How can I solve the Log Pile wooden puzzle with a computer program?_问答_开发者

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 un开发者_运维问答til 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.

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.

Prolog is popular for problems of this type. I've set up some simpler puzzle problems that have relatively nice solutions in Prolog.

There are very elegant ways of solving these kinds of problems in Haskell, using functions and backtracking. A friend of mine solved a very vexing physical puzzle—Puzzling Pets—in just over 200 lines, of Haskell, including descriptions of all the pieces and everything. A good way to learn the relevant techniques would be to read John Hughes's paper Why Functional Programming Matters, install the Haskell Platform, and try your hand.

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.

I have a (messy!) solution in javascript, but have had difficulty posting it. The basic algorithm used is: Find all iterations of 5 logs from the total of 10 logs, and with each set of 5 logs create every iteration possible with logs being reversed. For each of these states, we will know what pattern of logs will need to be placed on top. So, we then determine if the remaining 5 logs are able to to be placed on top.

Which leads to this representation of a solution:

(Bottom, right-> left)  
[0,0,1,-1,1],[-1,-1,0,0,-1],[0,0,1,0,1],[-1,1,0,-1,0],[1,0,-1,0,0]  
(Top, up->down)  
[0,1,0,1,-1],[0,1,0,-1,0],[-1,0,-1,0,1],[1,0,0,1,0],[-1,1,-1,0,0]  


0 - flat   
1 - dowel  
-1 - hole