Answers.Body: <p>Using your app, I was able to find a (spoiler alert!) <a href="https://i.sstatic.net/TQlIZ.jpg" rel="nofollow noreferrer">solution</a> manually. At least now you know your puzzle is solvable and you did not waste your money :)</p>
  
  <p>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. </p>
  
  <p>Now the idea. It may be useful for your solver.</p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>I don't know how to write an efficient solver either. For starters:</p>
  
  <ol>
  <li>Build up a list of bad configurations: small sets of pieces/positions such that whenever you reach them, you know there is no hope.</li>
  <li>At each step, put a piece in such way it minimizes the number of forced empty squares. </li>
  <li>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. </li>
  <li>Lookup whether this puzzle is known. Names that come to mind: Martin Gardner, Ian Stewart, Sam Lloyd. </li>
  </ol>
  
  <p>Can't say you will ever be able to see a list of all possible solutions. </p>
  
  <p>Nice puzzle, nice app that one you wrote, I've had a good time. Thank you.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-19T23:33:11.203Z
Answers.Text: 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.
Answers.UserDisplayName: Nizam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-20T00:16:06.677Z
Answers.Text: 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.
Answers.UserDisplayName: rts
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-19T22:28:22.290Z
Answers.LastActivityDate: 2019-05-20T00:18:34.183Z
Answers.LastEditDate: 2019-05-20T00:18:34.183Z
Answers.UserDisplayName: rts
Body: <p>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 <a href="http://www.xams.com.br/quebra" rel="nofollow noreferrer">http://www.xams.com.br/quebra</a>. It is possible to turn the piece 90 degrees each time counterclockwise (<em>Girar</em>) and mirror it vertically (<em>Inverter</em>), and so the piece can assume 8 forms.</p>
  
  <p>When clicking in solver button (<em>Resolver</em>), it tries to put pieces randomly in board in brutal force method (it spends a <strong>LOT</strong> of time). Using this method, I was not able to achieve the result.</p>
  
  <p>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?</p>
  
  <hr>
  
  <p><strong>EDIT:</strong>
  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.</p>
  
  <hr>
  
  <p><strong>EDIT2:</strong>
  <a href="https://i.sstatic.net/eq7iY.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eq7iY.jpg" alt="enter image description here"></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-12T19:23:33.123Z
Comments.Text: Are you sure it is actually possible at all to complete?
Comments.UserDisplayName: benbyford
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-12T19:26:43.230Z
Comments.Text: 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)
Comments.UserDisplayName: Nizam
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-13T00:04:47.597Z
Comments.Text: 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.
Comments.UserDisplayName: Hanzy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-13T17:35:05.177Z
Comments.Text: 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.
Comments.UserDisplayName: Benedikt S. Vogler
Tags: <machine-learning><ai-design><game-ai><combinatorial-games>
Title: How do I solve the problem of positioning 11 pieces into a 8x8 puzzle?
UserDisplayName: Nizam
ThreadText: # How do I solve the problem of positioning 11 pieces into a 8x8 puzzle?
  
  (Asked by: username_0 on 2019-05-12)
  
  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](https://i.sstatic.net/eq7iY.jpg)](https://i.sstatic.net/eq7iY.jpg)
  
  **Tags:** machine-learning, ai-design, game-ai, combinatorial-games
  
  > **Comments:**
  > **username_1**: Are you sure it is actually possible at all to complete?  
  > **username_0**: 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)  
  > **username_2**: 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.  
  > **username_3**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2019-05-19. Score: 3
  
  Using your app, I was able to find a (spoiler alert!) [solution](https://i.sstatic.net/TQlIZ.jpg) 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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_4**: 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.  
  
  ---
  
  