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.