I am currently trying to write a program to make a 3d version of a puzzle I own. The idea of the puzzle is to fit blocks of different shapes and sizes into a cube without having any parts sticking out at the end. There are thirteen different pieces that can each be rotated in twenty-four directions. Each piece is made up of a number of cube units. The size of the box is 4 units * 4 units * 4 units. Here are pictures of the pieces in the puzzle Each piece can be rotated on the X Y or Z axis by 90 degrees at a time. 7 of the pieces have 24 different orientations, 5 of the pieces have 12 different orientations(because they are the same shape when turned upside down) and piece12 (the last red piece show on the web page above) has only 3 different orientations. I have also figured out how many different positions each piece can be placed in in the box. (piece0:432, piece1:216, piece2:432, piece3:384, piece4:192, piece5:432, piece6:216, piece7:324, piece8:216, piece9:432, piece10:432, piece11:576, piece12:48) I hope to write different algorithms to try to solve the puzzle and compare how each of them works. I am fairly new to this type of problem however and would like a few suggestions of what type of algorithms would be most useful. I have read up on genetic algorithms but find it hard to understand how I could implement this for this type of problem. This is my final year project and I have been encouraged to seek help from experts and people who are knowledgeable in this area. Any suggestions would be greatly appreciated.

I guess the no-homework policy would apply to this thread. Anyway, just start with a simple depth-first search. If you write it right it should be fast enough and you won't need fancy algorithms.

Depth first search is the simplest way. You just try placing each block somewhere in the puzzle. If a position is invalid (because it would overlap another block), you try the next position for that block. If there are no valid positions for a block, you backtrack and go back to trying other positions for the previous block.

There is a paper by Donald Knuth that describes what he calls the dancing links algorithm, which can be downloaded from his web site. It is more complicated than a simple depth first search. It is directly applicable to this problem (the paper demonstrates the solutions it found for other block puzzle problems). It's probably one of the most sophisticated ways to solve this problem.

This is an interesting problem.

The key here seems to be that due to the various orientations and positions of the blocks, a depth first search might take very long....yeah, looking at the possible positions its pretty nasty.

I guess I shouldn't give you the whole genetic algorithm solution, but here are a few tips to help you on your way.

1. You probably don't need to use a binary coded GA. Since you have a fixed number of blocks, your chromosome or candidate solution will just be a combination of the blocks in a certain combination of orientations/positions.

2. Your fitness function can simply be, given a combination of block orientations, how many cubes overlap and how many stick out of the 4x4x4 boundary. The goal of course is to reduce it to 0.

3. Mutation should be pretty straight forward as you can simply randomly choose an orientation for a block.

4. Crossover shouldn't be tough once you get the above stuff to fall into place.

5. Remember, these are only ideas, you may need to hack them a bit as you learn more about the problem.

As for other approaches, there is one that comes to mind. You can read up on Tabu Search. Using the same fitness as above, you can probably get tabu search to work. You might even try simulated annealing too.

Just another tip, don't be afraid to hybridize. Good hybrid algorithms may sometimes work better than the original.

There are too many combinations for a depth first search. I'll give the genetic algorithm a try. Thanks for the help.

You should really try both. The depth first search algorithm, if implemented correctly, is guaranteed to find a solution if given enough time.

The genetic algorithm is a probabilistic algorithm, so it should also eventually find a solution if given enough time, but the parameters for tuning it may lead it to waste a lot of time repeatedly exploring states that aren't near the solution.

The dancing links algorithm is almost certainly better than the other options presented. More general constraint satisfaction problem solving algorithms can also do well.

A suggestion:
I think Depth First Search might be quite feasible, you just need to make it clever about optimizations.

You may have opportunities to Early Out Reject on many of the Depth Search branches.
For example.... if the placement of a new piece 'cuts off' an empty cube by itself (so it is surrounded by either walls or filled spaces), this configuration must be bad since there will never be a way to fill in that empty space. -this idea can be extended, so instead of finding a 'island' of a single empty cube, also watch for clusters of empty cubes that are smaller than the smallest available piece. (in terms of bounding dimensions)

I'd also, when Depth Searching, Only search positions for new pieces where they are Touching previous pieces. That should lower the possible branches by quite a lot! It does not exclude the search from visiting all possible Valid configurations, its just a nice way to help avoid repeating yourself. Plus checking configs where the new piece touches the previous ones also increases the chances of finding the above mentioned 'cut off' empty cubes.

Doing both of those at once makes the search more similar to what a human (me) would do when solving the puzzle - new peices contact old ones and 'islands' of empty space are avoided; so you basically try and Fill In space as compactly as possible.
If you want, you could even add in a 'gravity' effect when placing new pieces (first piece must touch bottom of cube, later peices must rest on previous ones), that should help cull the branches even more, and help to eliminate Symmetryies in the search (reduced to 1/6 the size I'd bet).
-hey if that approach works for a human... why not for the program as well?

Actually, what you guys are referring to is not exactly depth first search, its more like Backtracking search used for constraint satisfaction problems. It is not hard to implement as the origianl purpose was to cut down on futile branching. However, you still run into massive thrashing problems.

For example, after placing the 4th piece successfully, you start placing the 5th, but you iterate through all the possible positions and orientations of possible 5th pieces and find that nothing works, because of possible contraint violations down the line. So, you back track and replace the 4th piece. However, in reality, the problem may be that the 2nd piece wasn't right in the first place. But to realise that, the search must go through all possible 3rd, 4th and 5th piece combinations or more before coming back to change the second piece. So, in the current problem, if we've put in piece0 first, then piece1 second, and piece1 is in the wrong position, you won't know till you try combinations of the rest of the 10 pieces. So, assume that 3 more pieces is as far as the search goes before backtracking to change the second piece, you're still searching at least 192x48x216 possibilities and thats a minimum.

Probably the better way, if you really want to use backtracking style searches, is to use a weak-commitment search, which performs 2 - 10 times better than the best backtracking. But based on the size of the search space, that's still gonna take pretty long.

Sorry, I've sort of rambled on, but just wanted to point out the real downside to using backtracking style searches, since we are lookin at a search space of about 10^38 and pruning can only really go so far.

This is an NP-complete problem, so even in the best case it will not be very efficient. It is an example of the "3D bin packing problem" for arbitrary solids.

Since you know the geometry of the pieces you have a few heuristics that can help you in cutting down the search quickly.