Hello,
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 combining a shape in a feasable way that takes care of 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 to understand what I mean..
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.
As it is a more or less small problem because for a computer there is a small number of combinations possible I would try a simple search algorithm. I mean an algorithm that checks every possible configuration and goes on from the result of this configuration until it ends up in a end configuration, in your case the cube.
The problem seams to be writing a program that is able to do all the state checks and transformations from one state to another. Because you have to see if the configuration is physically possible.
Seems like an easier subset of a three-dimensional polyomino packing problem. There are various scholarly papers on that subject.
If the puzzle you want to handle is that one in the photo you have linked, then it's probably feasible to just search through a tree of possible solutions until you find your way to the bottom.
If each puzzle piece is a number of cubes attached at their faces, and I am to solve the puzzle by fitting each piece into a larger cube, 4 times on each edge as the composing cubes, then I'd proceed as follows.
Declare an arbitrary cube of each piece as its origin. Observe that there are 24 possible rotations for each puzzle piece, one orientation for each possible face of the origin cube facing upwards, times 4 possible rotations about the vertical axis in that position.
Attempt to cull the search space by looking for possible orientations that produce the same final piece, if a given rotation, followed by a translation of the origin cube to any of the other cubes of the piece results in exactly the same occupied volume as a previously considered rotation, cull that rotation from future consideration.
Pull a piece out of the bag. If there are no pieces in the bag, then this is a solution. Loop through each cell of the solution volume, and each rotation of the pulled piece for each cell. If the piece is completely inside the search volume, and does not overlap with any other piece, recurse into this paragraph. Otherwise, proceed to the next rotation, or if there are no more rotations, proceed to the next cell, or if there are no more cells, return without a solution.
If the last paragraph returns without a solution, then the puzzle was unsolvable.
