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.