CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: What is the optimal solution for the game "Puzzle+"?

1. Junior Member
Join Date
Mar 2015
Posts
9

## 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)?
Last edited by MkJones; March 9th, 2015 at 05:38 PM. Reason: Fixed-width font for the example

2. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: What is the optimal solution for the game "Puzzle+"?

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 )

3. Junior Member
Join Date
Mar 2015
Posts
9

## Re: What is the optimal solution for the game "Puzzle+"?

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?

4. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: What is the optimal solution for the game "Puzzle+"?

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 ).
Last edited by superbonzo; March 9th, 2015 at 04:06 PM.

5. Junior Member
Join Date
Mar 2015
Posts
9

## Re: What is the optimal solution for the game "Puzzle+"?

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

6. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## Re: What is the optimal solution for the game "Puzzle+"?

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.

7. Junior Member
Join Date
Mar 2015
Posts
9

## Re: What is the optimal solution for the game "Puzzle+"?

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
Last edited by MkJones; March 10th, 2015 at 03:23 PM.

8. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## Re: What is the optimal solution for the game "Puzzle+"?

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```

9. Junior Member
Join Date
Mar 2015
Posts
9

## Re: What is the optimal solution for the game "Puzzle+"?

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|

10. Member +
Join Date
Jul 2013
Posts
576

## Re: What is the optimal solution for the game "Puzzle+"?

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.
Last edited by razzle; March 12th, 2015 at 01:47 AM.

11. Junior Member
Join Date
Mar 2015
Posts
9

## Re: What is the optimal solution for the game "Puzzle+"?

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.
Last edited by MkJones; March 12th, 2015 at 04:25 AM. Reason: Fixed code formatting

12. Member +
Join Date
Jul 2013
Posts
576

## Re: What is the optimal solution for the game "Puzzle+"?

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).

13. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## Re: What is the optimal solution for the game "Puzzle+"?

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.

14. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## Re: What is the optimal solution for the game "Puzzle+"?

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 2M 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.

15. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## Re: What is the optimal solution for the game "Puzzle+"?

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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•