
March 9th, 2015, 10:41 AM
#1
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[x1][y], array[x+1][y], array[x][y1], array[x1][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 bruteforce solution. Can any one advice an efficient approach? O(n)?
Last edited by MkJones; March 9th, 2015 at 05:38 PM.
Reason: Fixedwidth font for the example

March 9th, 2015, 01:07 PM
#2
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 )

March 9th, 2015, 02:14 PM
#3
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?

March 9th, 2015, 03:54 PM
#4
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.

March 9th, 2015, 04:25 PM
#5
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 precomputing (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

March 10th, 2015, 09:02 AM
#6
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.

March 10th, 2015, 03:17 PM
#7
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.

March 11th, 2015, 08:48 AM
#8
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 rowmax1
if cell(row,0) or cell(row,colmax)
then abort, unsolvable state
for column 1 to colmax1
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

March 11th, 2015, 04:19 PM
#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

March 12th, 2015, 01:22 AM
#10
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.

March 12th, 2015, 04:21 AM
#11
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..M1 # scan from second row
for X in 0..N1 # scan all columns
if board[X][Y1] # 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 precalculating 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

March 12th, 2015, 06:07 AM
#12
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 secondmost 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).

March 12th, 2015, 08:43 AM
#13
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.

March 12th, 2015, 09:30 AM
#14
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 2^{M} possible patterns in the bottom row.
There might be a mathematical deduction method to figure out the toptobottom 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.

March 12th, 2015, 09:49 AM
#15
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 gaussjordan 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.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
