How is this game called?

[S G H]

@giblit: I meant combinations given a specific starting table.
Anyways, as I said above, I probably have a bug that prevents the loop to repeat, checking the table after computing the first "table pass".

[Danny Toledo]

There should be 12 if my math is correct since

*hint* Think of the board as representing a binary number. Each grid has n elements and each element can hold one of two possible states:

     a   b
   ---------
1  | 1 | 1 |
   ---------
2  | 0 | 1 |
   ---------
^
||
v
a1|b1|a2|b2
-------------
| 1| 1| 0| 1|
-------------

We know that an n bit integer can hold 2ⁿ unique values: 0 to 2ⁿ-1. For a 2x2 grid, n = 4. 2⁴ = 16.

For a 3x3 grid, we get 2⁹=512, so there are 512 different possible grids.

One possible solution to this that I just thought up in the shower:

Make a graph with 512 (for a 3x3 grid, adjust for other sizes) vertices (representing each possible "state" of the grid). For each vertex, try each possible move and record which vertex that leads to (that is, there will be an edge between the two vertices, possibly labeled with what move was used [we may want this later]). Once that is done, start at either of the winning states (we'll call them vertex 0 and vertex 511). From this point you just need to search for a path from a winning state to the input state (and you will likely need to mark each vertex as visited otherwise you may wind up in a never ending cycle). As you are searching, if you labeled the edges with the move that gets you from one state to another, you can record one possible solution (instead of just reporting that a solution exists).

I may be incredibly off, but in my mind that should work.

[giblit]

We know that an n bit integer can hold 2n unique values: 0 to 2n-1. For a 2x2 grid, n = 4. 24 = 16.

that makes a lot more sense to me, I wasn't even thinking about that at the time I posted.