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

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

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

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

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

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 )

2. Junior Member
Join Date
Mar 2015
Posts
9

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

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"

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.

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

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

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

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

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

4. Junior Member
Join Date
Mar 2015
Posts
9

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

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

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

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

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

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

6. Junior Member
Join Date
Mar 2015
Posts
9

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

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

7. Member +
Join Date
Jul 2013
Posts
576

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

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.

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

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

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

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

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

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

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

10. Member +
Join Date
Jul 2013
Posts
576

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

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.

#### Posting Permissions

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