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

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

  1. #1
    Join Date
    Mar 2015
    Posts
    9

    Question 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. #2
    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. #3
    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. #4
    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. #5
    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. #6
    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. #7
    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. #8
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

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

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

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

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

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

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

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

    Quote Originally Posted by MkJones View Post
    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. #13
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

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

    Quote Originally Posted by MkJones View Post
    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. #14
    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. #15
    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.

Page 1 of 2 12 LastLast

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)