20
$\begingroup$

I have this wooden puzzle composed of 25 y-shaped pentominoes, where the objective is to assemble them into a 5x5x5 cube. After spending quite a few hours unsuccessfully trying to solve the puzzle, I finally gave up and wrote a program to try all possible combinations using backtracking. Analyzing the results revealed that for every solution found, the computer made - on average - 50 million placements and removals of pieces. This is obviously beyond my capabilities as a human, even if I can see a few steps ahead that a partial solution leads to a "dead end".

So, my question is this: given that the puzzle is so symmetrical, is there some way to significantly prune the search tree (maybe even making it possible for me to solve the puzzle on my own)?

alt text

(sorry for the poor quality)

  • 0
    yes you can certainly factor out the symmetries of the cube. It might also be fruitful to consider - for a single cube of the puzzle, that since it must be filled then what are all the possible ways to place a pentomino that fills that cube (now you know that one of these must be the correct one). Another good optimization (which is harder to implement) is to try to find impossibilities as quickly as possible (since that prunes the search tree you will get to the solution quicker).2010-08-21
  • 0
    @muad, I'm looking for something _really_ significant. Eliminating symmetries only reduces by a factor of 24. Can you elaborate on finding impossibilities?2010-08-21
  • 0
    Actually, I think the wording is not clear. What I'm really looking for is some mathematical property that would eliminate the need to do backtracking on combinations of piece placements.2010-08-21
  • 0
    Personally, I would construct the corner presented in the picture, then attempt the second half of the puzzle as normal. This would also prune your search tree considerably given a known starting configuration in which a solution exists.2010-08-22
  • 0
    You can't do it without backtracking.2010-08-22
  • 0
    @muad, can you explain why?2010-08-22
  • 0
    Since it's related to NP-hard problems. I hope someone with more knowledge on this could elaborate a bit.2010-08-22
  • 2
    @muad, the general problem may be NP-hard, but this is but *one instance*: there is no reason a priory why particular instances of very hard problems can be solved using special tricks adapted to the instance.2010-09-13
  • 0
    How many solutions are there? Also, when you say "50 million placements and removals", I assume invalid moves are not counted as (attempted) placement.. correct? The reason I'm asking is the program I wrote does a simple exhaustive search (starting from one of the corners of the grid) and finds 20 solutions in ~95 million moves, less than 5 million moves per solution on average. I'm curious about what you and I did differently. Thanks, Leor2011-03-13
  • 0
    @Leor: please stop posting comments as answers, especially after the first one was converted for you. Repeated posting of duplicate content will be seen as spamming.2011-03-13
  • 0
    According to the site you linked to, polyominoes are ***plane*** geometric figures. I think the word you want is [polycubes](https://en.wikipedia.org/wiki/Polycube). Also, your question is not about "tiling pentominoes" (or polycubes), it's about tiling a cube with polythings.2016-06-26

5 Answers 5