-
March 12th, 2015, 11:23 AM
#16
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 )
-
March 12th, 2015, 12:37 PM
#17
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
-
March 12th, 2015, 01:20 PM
#18
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 ...
-
March 12th, 2015, 01:48 PM
#19
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|
-
March 12th, 2015, 03:32 PM
#20
Re: What is the optimal solution for the game "Puzzle+"?
-
March 12th, 2015, 05:05 PM
#21
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
-
March 13th, 2015, 12:18 AM
#22
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.
-
March 13th, 2015, 05:56 AM
#23
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...
-
March 13th, 2015, 09:35 AM
#24
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. :-)
-
March 13th, 2015, 04:58 PM
#25
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.
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
|