Which is the best way to solve this kind of game?

Question

This evening I tried to solve a wood puzzle so I wondered which is the best way to find a solution to this kind of problem programmaticaly.

The aim is to combine a set of solids (like tetris pieces in three dimensions) together to form a shape in a feasable way that takes into account the fact that pieces can be attached or slided into the structure only if they fit the kind of movement (ignore rotations, only 90° turns).

Check this picture out to understand what I mean.

Answer 1

In my latest CS class we made a generic puzzle solver that worked by having states represented as objects in C++. Each object had a method to compare the state it represented to another state. This was used for memoization, to determine if states had already been seen. Each state also had a method to generate states directly reachable from that state (i.e. rotating a block, placing a block, shifting a block). The solver worked by maintaining a queue of states, popping a state off the front of the queue, checking to see if it was the desired state (i.e. puzzle solved). If not, the memoization (we used a hashed set) was checked to see if the state had already been seen. If not, the states reachable from the current state were generated and appended to the rear of the queue. An empty queue signaled an unsolvable puzzle.

Conceptualizing something like that for 3D would be hard, but that is the basic approach to computerized puzzle solving.