How can I solve the Log Pile wooden puzzle with a computer program?

Question

Can anyone suggest how to solve the Log Pile wooden puzzle using a computer program?

See here to visualise the puzzle: http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm

The picture only shows some of the pieces. The full set of 10 pieces are configured as follows with 1 representing a peg, -1 representing a hole and 0 representing neither a peg nor a hole.
-1,1,0,-1,0
1,0,1,0,0
1,-1,1,0,0
-1,-1,0,0,-1
-1,1,0,1,0
0,1,0,0,1
1,0,-1,0,-1
0,-1,0,1,0
0,0,-1,1,-1
1,0,-1,0,0

The pieces can be interlocked in two layers of 5 pieces each with the top layer at 90 degrees to the bottom layer as shown in the above link.

I have already created a solution to this problem myself using Java but I feel that it was a clumsy solution and I am interested to see some more sophisticated solutions. Feel free to either suggest a general approach or to provide a working program in the language of your choice.

My approach was to use the numeric notation above to create an array of "Logs". I then used a combination/permutation generator to try all possible arrangements of the Logs until a solution was found where all the intersections equated to zero (ie. Peg to Hole, Hole to Peg or Blank to Blank). I used some speed-ups to detect the first failed intersection for a given permutation and move on to the next permutation.

I hope you find this as interesting as I have.

Thanks, Craig.

Answer 1

This problem appears to be a form of the Boolean satisfiability problem. If it is, the best known approach is brute force.

But there are some symmetries, and some properties of the problem that can let you reduce the number of solutions you need to try. For instance --

• If you divide the logs into two 5-piece subsets TOP and BOTTOM, the # pegs in TOP needs to match the # holes in BOTTOM, and the # holes in TOP needs to match the # pegs in BOTTOM, and the # flats in TOP needs to match the # flats in BOTTOM. If the # pegs and # holes match up, then the # flats will match as well, so you should not need to check the # flats.
• There are 10 * 9 * 8 * 7 * 6 ways you can partition the logs into two 5-piece subsets. (Once you have picked the first 5 logs for subset TOP, the remaining logs are in subset BOTTOM.
• When you test a 5-piece subset, there are 5 * 8 * 6 * 4 * 2 ways you can arrange one layer of logs. That is, after you pick log 1, there are 4 remaining logs. For the second log, you can pick from four, and there are two ways it can be oriented with respect to the first log.
• Once you have a base layer, you can try to fit each log from the other layer one at a time, until you find one that does not fit. At that point, you give up on the current base layer log arrangement and try the next one.

Answer 2

Following the advice by Jay Elston, I would implement it using the following pseudocode:

 Read in the pieces
 Annotate each piece with its number of pegs and holes
 Generate all possible base layers (10 over 5 = 252, selecting 5 from the set), 
   so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes)
   For each base layer, (5! = 120 of them, permuting the 'below' pieces)
      compute 'rotated pieces' for the base layer
      if one-to-one match between top layer and rotated base-layer pieces, 
          report successful solution

Where the "rotated pieces" would be, for a given base layer, the ideal pieces you would need to cover it. By computing these pieces and matching them with the top layer pieces, you can use a O(N log N) sort to match rotated pieces against real top layer instead of matching against all N! possible top layer arrangements. Plus, at the first non-match, you can bail out early.

The key to writing efficient algorithms is to prune your search as early as possible, and to exploit any symmetries. For example, you can cut run-time by half if you figure that the puzzle is symmetrical, and therefore you arbitrarily assign a piece to the bottom layer: you will then have only 9 over 4 base layers to explore.