3
$\begingroup$

I was trying to figure out how to create a solver to the puzzle of putting 11 pieces in a board (8 x 8). I created the game in http://www.xams.com.br/quebra. It is possible to turn the piece 90 degrees each time counterclockwise (Girar) and mirror it vertically (Inverter), and so the piece can assume 8 forms.

When clicking in solver button (Resolver), it tries to put pieces randomly in board in brutal force method (it spends a LOT of time). Using this method, I was not able to achieve the result.

I would like to try something smarter than this and having a machine learning algorithm for this would be great. I don´t know how to formulate the problem. How would you start this please?


EDIT: I am still building the page and there is so much to improve. You need to click the center of 3x3 matrix where you want to put the piece.


EDIT2: enter image description here

$\endgroup$
  • $\begingroup$ Are you sure it is actually possible at all to complete? $\endgroup$ – benbyford May 12 at 19:23
  • $\begingroup$ I bought this puzzle (physically) and hope it is possible. I could put 10 pieces. I think they would not sell this is it was not possible (I hope so) $\endgroup$ – Nizam May 12 at 19:26
  • $\begingroup$ Can this not be solved with MCTS? Just start a piece in one position and try every combination down the tree. If it’s solvable it should be able to find the solution. $\endgroup$ – Hanzy May 13 at 0:04
  • 1
    $\begingroup$ I think the machine learning tag is wrong, as there is nothing to learn. I solved a similar problem once with a recursive backtracking algorithm. With brute force it is basically unsolvable. $\endgroup$ – Benedikt S. Vogler May 13 at 17:35
3
$\begingroup$

Using your app, I was able to find a (spoiler alert!) solution manually. At least now you know your puzzle is solvable and you did not waste your money :)

It seems your app has a bug, though. I was unable to put the last piece, as shown in the picture. I was wondering if your solver, as it stands, will ever find a solution.

Now the idea. It may be useful for your solver.

The board has 8x8=64 squares. Each piece will occupy 5 squares and you want to fit 11 pieces, so the final position will have 9 empty squares. Divide the board in two 8x4 rectangles, left and right. Now, it seems only fair that one rectangle should have 5 empty squares leaving the other with 4; with that in mind I've proceeded to fill the right part first and only then the left. After some trial and error, I got lucky.

I don't know if you can reach all solutions with this method. Notice that, in the solution given above, the bottom rectangle will end up with 6 empty squares.

I don't know how to write an efficient solver either. For starters:

  1. Build up a list of bad configurations: small sets of pieces/positions such that whenever you reach them, you know there is no hope.
  2. At each step, put a piece in such way it minimizes the number of forced empty squares.
  3. A variant of the idea above: divide the board in four 4x4 parts; it seems reasonable each part should have at least one empty square but no so many; so, look for solutions forcing these parts to have (1,2,3,3) or (2,2,2,3) empty squares.
  4. Lookup whether this puzzle is known. Names that come to mind: Martin Gardner, Ian Stewart, Sam Lloyd.

Can't say you will ever be able to see a list of all possible solutions.

Nice puzzle, nice app that one you wrote, I've had a good time. Thank you.

$\endgroup$
  • $\begingroup$ I will try the methods you sugested and will be a huge pleasure to mark your answer as the accepted one. I am ver glad that you solved the puzzle. Thanks a lot and congratulations. $\endgroup$ – Nizam May 19 at 23:33
  • $\begingroup$ Thanks! By the way, I was thinking, maybe you could write a game: say two players, each one put one piece at a time; the first one that could not put a piece loses. You could play on even larger boards, say 10x10, 13x13, etc. That would be hard. And then definitely some AI programming could come in. $\endgroup$ – rts May 20 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.