All Possible Combinations in Grid

Question

Ok so this has been bothering me for a while and I've sort of just hit a wall. So say you have a square grid represented as a two dimensional array and each cell can be in one of two states. How would you go about building a list of every possible combination that could exist in said grid? I realize that this is impractical for larger grids but for something small like say 5x5 or smaller I imagine it would be possible to simply enumerate every possible combination.

Also for the record I'm trying to solve the nurikabe puzzle and find every possible configuration. I have a bunch of other stuff to prune with but building the original list of possible configurations is killing me

Answer 1

For a 5x5 square, there are 2^25 possible combinations.

So you can use a 32-bit integer in order to represent one.

---

Here is a function that converts an integer into a square:

void Id2Square(const unsigned int& id,bool square[SIZE][SIZE])
{
    for (int n=0; n<SIZE*SIZE; n++)
        square[n/SIZE][n%SIZE] = (bool)((id>>n)&1);
}

Here is a function that converts a square into an integer:

void Square2Id(unsigned int& id,const bool square[SIZE][SIZE])
{
    id = 0;
    for (int n=0; n<SIZE*SIZE; n++)
        id |= (unsigned int)square[n/SIZE][n%SIZE]<<n;
}

---

So if you want to check all possible squares, for example, then you can do it as follows:

void CheckAllSquares()
{
    bool square[SIZE][SIZE];
    for (int id=0; id < 1<<(SIZE*SIZE); id++)
    {
        Id2Square(id,square);
        // Now do whatever you want to do with 'square'
    }
}

Answer 2

You can think of this as simply an n*n binary number where n is the size of a side of your square grid. At this point all you have to do is count up from 000...0 (n zeros) to 111...1 (n ones) in binary and save each number. You could then convert this into an array format if you wanted by running through the binary number and after every n number of bits go to the next line in the array.