What is the optimal solution for the game "Puzzle+"?

A friend challenged me to find an algorithm to solve the game Puzzle+:

In a nutshell: given a NxM array of random booleans, your objective is turn all values to false.
On each move you specify a coordinate (x,y) to toggle (array[x][y] = not array[x][y]), however that action also affects array[x-1][y], array[x+1][y], array[x][y-1], array[x-1][y+1] (on in short - it's adjacent cells).

For example: given a 3x3 board:

|f T f|
|T T T|
|f T f|

The solution it to simply toggle the middle cell.

You can find the actual game here: https://play.google.com/store/apps/d...pps.puzzleplus (android only)

I could only come up with a brute-force solution. Can any one advice an efficient approach? O(n)?

an hint: you can think at the set of input matrices as the vector space of matrices over the field Z2 ( that is, modulo 2 arithmetic matrices ) then each "move" consists in summing one of the "neighbourhood" matrices ( that is a matrix with all zero but a "cross" of one's, as in your 3x3 example ); now, if the problem has always a solution and being such matrices NxM ( = the dimension of the vector space ) these must form a base; so, the solution can be found in O(NxM) time via a base transformation ... ( that is, by precomputing the canonical base in terms of the aforementioned "moves" base )

not sure I understand you -- do you wish to precompute a solution for every single cell (separately) and then combine them (add modulo 2) according to the given matrix?

yes I do, ( unless I missed something about the problem formulation ) it should work ...

PS: just a clarification: by "precomputing" I did't mean to actually store them somewhere in a sort of look up table ... I mean that you could compute all of them programmatically ( due to the symmetry of the problem, if you got it for any entry inside, at the sides and at the corners of a generic NxM matrix you should be able to compute them all ).

how would you do it in O(NxM) without a lookup table? the symmetry saves you only half the pre-computing (or three quarters when N=M)

--

i found another way to solve it, i realized that i only need to guess the first row, cells in the 2nd..Nth rows should be toggled in places that clear the row above them. it's O(2^N) complexity, but for 16x16 it's still blazing fast :)

unless you're allowed to flip the 'center' of the cross when it's outside of the NxM.
This doesn't even have a guaranteed solution if the input is indeed "random" as the OP indicates.

the center must be within bounds; there is a guaranteed solution for all puzzles given in the game, however not necessarily for any random initial state (that depends on the board's shape).

PS: optimal solution - both in terms of computation complexity and the number of moves required for the solution

Quote:

---

Originally Posted by MkJones

the center must be within bounds; there is a guaranteed solution for all puzzles given in the game, however not necessarily for any random initial state (that depends on the board's shape).

PS: optimal solution - both in terms of computation complexity and the number of moves required for the solution

---

in that case the solution strategy is simple and proovably optimal.
1) Any T on a corner indicates an unsolvable state -> break ouf of the program
2) Any T on the outer edge can only be flipped by flipping the 'cross' it's a part of, and there can be only 1 such cross.
3) If any edge only has F, then you can reduce the problem to a smaller rectangle by removing that edge.

or in pseudo code

Code:

---

for row 0 to rowmax-1
  if  cell(row,0) or cell(row,colmax)
        then abort, unsolvable state
  for column 1 to colmax-1
      if  cel(row, col)
            flip cross at row+1,col

test if rowmax has all false cells, abort unsolvable state if this is not the case

---

Quote:

---

1) Any T on a corner indicates an unsolvable state -> break ouf of the program

---

Not true, for example:

1 - toggle top left ; 2 - top right ; 3 - bottom left ; 4 - bottom right

|T T| --> |F F| --> |T T| --> |F T| --> |F F|
|T T| (1) |F T| (2) |F F| (3) |T T| (4) |F F|

Quote:

---

Originally Posted by MkJones

i found another way to solve it, i realized that i only need to guess the first row, cells in the 2nd..Nth rows should be toggled in places that clear the row above them. it's O(2^N) complexity, but for 16x16 it's still blazing fast

---

What do you man by guessing the first row?

You can clear a row by toggling the row immediately underneath it. This means the whole top of a board can be very cheaply cleared leaving 3 rows at the bottom that must be solved using a more complex toggling strategy.

With this initial clearing (if we consider 3 by 3 boards and bigger) the general N by M problem can be reduded to a much smaller 3 by M where only the 2 bottom rows are open for toggling.

In other words, find a solution to the 3 by M problem by toggling the 2 bottom rows only. If that's possible it also solves all N by M problems.

Quote:

---

Originally Posted by razzle

What do you man by guessing the first row?

---

Given that the puzzle has at least one solution, we'd like to find the one with the least amount of moves. A naive approach is to scan all 2^(N*M) options. My solution is to guess all 2^N options for a first row (as I mentioned N is not too high). For each guess we are no longer allowed to toggle columns on the first row (no point in that -- all the guesses will cover it anyway). So --

Code:

---

for each 1st row guess
  for Y in 1..M-1      # scan from second row
    for X in 0..N-1    # scan all columns
      if board[X][Y-1]  # if the cell above is T
        toggle(X, Y)    # toggling the current cell is the only possible move
  solved? ... reset board

---

It will find all possible solutions, finding is the minimal is of course trivial.

I'm looking for something more efficient... O(2^N) is better than O(2^NxM) -- it makes it a "usable" solution.
Note that pre-calculating a solution for each separate cell (and XOR'ing them) will only work for certain sizes of NxM.

Quote:

---

Originally Posted by MkJones

Given that the puzzle has at least one solution, we'd like to find the one with the least amount of moves.

---

I'll try to understand your strategy but I'm investigating a strategy that builds on the board reduction I mentioned.

From what I can see it's possible to clear the board down to the last two rows in O(N*M) time.

The problem has then become reduced to toggling the bottom row until it and the second-most bottom row becomes clear. It's not unthinkable that there's a simple toggling pattern that accomplishes this quickly in O(M) regardless of the initial state of the last two rows.

This may not be an optimal strategy for all initial boards but the algorithm would operate in O(N*M).

Quote:

---

Originally Posted by MkJones

Not true, for example:

1 - toggle top left ; 2 - top right ; 3 - bottom left ; 4 - bottom right

|T T| --> |F F| --> |T T| --> |F T| --> |F F|
|T T| (1) |F T| (2) |F F| (3) |T T| (4) |F F|

---

well now you contradict the statement that the cross needed to fall entirely within bounds.

anywho, if that can be done.
you just need a win strategy, even if suboptimal
then you can optimize the sequence of flips to it's optimal by removing any redundant pairs of identical flips.

Throwing some math at this, it would appear there is no single "win strategy" for this problem and a strategy is dependant on the size of the board.

there is a "generic approach strategy" but the 'bottom to top' pattern is diferent for each M and N.

Code:

---

for each row starting at top
      for any T in the row: flip the cross below it so you end up with all F
 depending on the pattern of T's in the (bottom) row
      there is a specific MxN dependant set of flips to do on the top row.
 // repeat the first loop for the 
 for each row starting at top
      for any T in the row: flip the cross below it so you end up with all F
// if you had the right bottom to top flips, it's now solved.
remove pairs of redundant flips to achieve optimal solution

---

you'll have to figure out the "top to bottom" patterns for all the MxN you need on your own. you can do this by trial and error. due to game mechanics there are (significantly) less than 2^M possible patterns in the bottom row.
There might be a mathematical deduction method to figure out the top-to-bottom flips, but I couldn't figure it out if there is one. I have patterns for a number of grid sizes, and they're verified through a couple thousand games each.

as far as I can tell, there is no other strategy to this. Though yes, a human might obviously see the solution "by eye" if only a few flips happened.

Should have realised this... "there is no other strategy" is a bit hasty...
I should have put 'there is no other human playable strategy'.

You can actually think of this problem as a matrix of a field domain in modulo 2.
And you can solve this in O(MxN) time using gauss-jordan elimination.
Already verified, random 1000x1000 board solved in just under a minute on a single core.
It would surprise me however this is the kind of solution your teacher is looking for.

yep, this is what I was hinting at in post #2 ( also, being the trasnformation matrix sparse, the inverse can be computed equally well by directly computing the base, it's a just a matter of paying attention to the matrix borders ).

Quote:

---

Originally Posted by OReubens

It would surprise me however this is the kind of solution your teacher is looking for.

---

why ? this looks like a typical linear algebra exercise ( at least in my country, linear algebra teachers have a notoriously sadistic attitude :) )

Quote:

---

Originally Posted by OReubens

well now you contradict the statement that the cross needed to fall entirely within bounds.

---

"the center must be within bounds"

Quote:

---

Originally Posted by OReubens

then you can optimize the sequence of flips to it's optimal by removing any redundant pairs of identical flips.

---

Consider a 4x4 board (marked "3" in the game) -

Code:

---

|T T T T|
|T T T T|
|T T T T|
|T T T T|

---

Two possible solutions:

Code:

---

|..x.| |xxxx|
|x...| |x..x|
|...x| |xxxx|
|.x..| |....|

---

I don't see how you "optimize" the right solution; the left solution (and it's symmetric variants) are the optimal solution.

Quote:

---

Originally Posted by OReubens

It would surprise me however this is the kind of solution your teacher is looking for.

---

My colleague :)

..
Now I just need to understand what you wrote :)

the right one seems not a solution at all ... ( or I totally missed the rules of the game :) )

Quote:

---

Originally Posted by MkJones

Now I just need to understand

---

as I tryed explaining in post #2, the fact that a solution always exists and the fact that z2-matrices form a vector space, implies that the "crosses" form a base ( = a maximal set of linearly indipendent vectors = a minimal ( = optimal) set of vectors ( = the moves ) whose linear combinations gives any other vector ( the input ) ); hence, a "solution" consists in expressing the input matrix in this new base, or equivalently inverting the base-to-base trasnformation matrix, or equivalently solving the associated linear system, etc...

so, for example, let's consider the 2x2 case; the transformation matrix mapping single-cells matrix to the corresponding "cross" is ( where the 2x2 matrices are counted starting from the top-right corner, clockwise ):

|1101|
|1110|
|0111|
|1011|

now, we need to invert that matrix that, in this fortunate case, is simply the matrix itself. So

given the input

Code:

---

|11|  |01|  |10|  |00|  |00|
|11| = |00| + |00| + |10| + |01| = (1,1,1,1) in the vector space of matrices wrt to the base above

---

the solution is

Code:

---

|1101| |1|  |1|
|1110| |1|  |1|
|0111|.|1| = |1| ( that is, toggle all )
|1011| |1|  |1|

---

given the input

Code:

---

|10|
|00| = (0,1,0,0)

---

the solution is

Code:

---

|1101| |0|  |1|
|1110| |1|  |1|
|0111|.|0| = |1| ( that is, toggle all but bottom-right )
|1011| |0|  |0|

---

etc ...

Quote:

---

Originally Posted by superbonzo

the right one seems not a solution at all ... ( or i totally missed the rules of the game :) )

---

Code:

---

|t t t t|    |f f t t|    |t t f t|    |t f t f|
|t t t t| -> |f t t t| -> |f f t t| -> |f f f t| ->
|t t t t| (0)|t t t t| (1)|t t t t| (2)|t t t t| (3)
|t t t t|    |t t t t|    |t t t t|    |t t t t|

|t f f t|    |f f f t|    |f f f f|    |f f f f|
|f f f f| -> |t t f f| -> |t t t t| -> |f t t t| ->
|t t t t| (4)|f t t t| (7)|f t t f| (8)|t f t f| (9)
|t t t t|    |t t t t|    |t t t t|    |f t t t|

|f f f f|    |f f f f|    |f f f f|
|f f t t| -> |f f f t| -> |f f f f|
|f t f f|(10)|f f t t|(11)|f f f f|   
|f f t t|    |f f f t|    |f f f f|

---

ok you're right sorry, I missed some t's ... :blush:

BUT ( yes, that's a big but :) )

the fact that more than one solution exists implies that the crosses do NOT actually form a base which in turn implies that the dimension of the space spanned by the crosses does not equal N*M, eg. that some crosses can be expressed as sums of other crosses ( you can see it one directly in your example ). But, this also implies that there must exist inputs with no solution, more specifically, those input matrices belonging to the kernel of the single-cell to cross transformation; one such vector is just the difference of yours two solutions:

Code:

---

|..x.|  |xxxx|  |xx.x|
|x...|  |x..x|  |...x|
|...x| - |xxxx| = |xxx.|
|.x..|  |....|  |.x..|

---

now, either the rhs matrix above has no solution ... or I must seriuosly refresh my linear algebra :) ...

first of all, thank you for the linear algebra refresh, it all adds up now.

I guess the question remains open, for NxM that are not injective :)

Quote:

---

Originally Posted by razzle

I'll try to understand your strategy but I'm investigating a strategy that builds on the board reduction I mentioned.

---

Well, it didn't work. Too bad. :)

Quote:

---

Originally Posted by MkJones

I guess the question remains open, for NxM that are not injective :)

---

what do you mean ? if our reasoning above is correct we have all we need to fully analyse the problem efficiently; basically, the algorithm could goes as follow:

given an NxM input I, build the (N*M)x(N*M) matrix Q mapping single-entry to "cross" matrices; if Q*I is zero than I has no solution; otherwise, use LUP factorization to find a solution ( it will be expressed in terms of vectors in Q image, whose dimension = rank of Q = minimal number of moves ). Note that being Q sparse the solution should be computable efficiently both in time and space ( there are a lot of ready to use libraries outthere for this purpose ).

as a further step, one could try to compute the above mathematically ( as we know the general form of Q ) or research for z2 optimized rank reveleaing fatorizations...

depending on N and M, not all random inputs have solutions. Playing with this some more it seems that the ones with an odd and even sided edge tend to be incomplete (though not necessarily so).

the 4x4 as you pointed out isn't :p

Quote:

---

I don't see how you "optimize" the right solution; the left solution (and it's symmetric variants) are the optimal solution.

---

Ah, but the issue here is then whether you could create a generalized wining STRATEGY that will result in the right side solution. :-)

Quote:

---

Originally Posted by OReubens

depending on N and M, not all random inputs have solutions.

---

My (failed) approach was to first clear the N by M board above the two bottom rows and then solve the remaining 2 by M board by just toggling the bottom line.

For an N by 3 board this didn't work because out of the 2^(3+3) = 64 possible inputs of the last two rows only 8 could be solved.