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

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you sure it is actually possible at all to complete? $\endgroup$
    – benbyford
    May 12, 2019 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, 2019 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, 2019 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, 2019 at 17:35

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2019 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, 2019 at 0:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .