Algorithm for solving 3d puzzle

neilkenny · 2005-12-04T13:54:45

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.