dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 25 of 25

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

  1. #16
    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 ).

    Quote Originally Posted by OReubens View Post
    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. #17
    Join Date
    Mar 2015
    Posts
    9

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

    Quote Originally Posted by OReubens View Post
    well now you contradict the statement that the cross needed to fall entirely within bounds.
    "the center must be within bounds"

    Quote Originally Posted by OReubens View Post
    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.


    Quote Originally Posted by OReubens View Post
    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. #18
    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 )

    Quote Originally Posted by MkJones View Post
    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. #19
    Join Date
    Mar 2015
    Posts
    9

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

    Quote Originally Posted by superbonzo View Post
    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. #20
    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. #21
    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. #22
    Join Date
    Jul 2013
    Posts
    576

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

    Quote Originally Posted by razzle View Post
    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. #23
    Join Date
    Oct 2008
    Posts
    1,456

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

    Quote Originally Posted by MkJones View Post
    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. #24
    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. #25
    Join Date
    Jul 2013
    Posts
    576

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

    Quote Originally Posted by OReubens View Post
    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.

Page 2 of 2 FirstFirst 12

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)