Mind blowing Puzzle Game!

The other day I was having a drink in the usual café and realized that the owner had put some mind games for the customers to experiment. Games such as the classic Rubik’s Cube and other puzzle games.

Most of the games were quite easy to solve, usually taking about 5 minutes. There was one though that blew my mind away. I spent more than 40 minutes trying out different approaches and none of them seem to get me anywhere else than frustration.

The game consisted in 13 pieces, that look like Tetris pieces, that one had to combine in order to and fit them inside a small squared board (8x8 individual positions).

Since I wasn’t going anywhere with the manual approach I thought:
- I’ll outsmart you, you little bastard, I make a program to solve you! And so, I copied the pieces onto a paper napkin and left home to program the solution (at 2 AM).

First I thought, this is a typical genetic algorithm (GA) kind of problem but I had no good GA libraries at hand, so I decided to do a full combinational approach, brute force that is. Trying all the possible combinations of all the pieces in all positions, in all possible rotations, and mirrored, adding up 13*4*2*8*8 = 6656 distinct pieces.

How wrong was I! The software takes roughly millions of years to compute all the solutions. We’re talking about 13^6656 possible combinations. It’s just too much, so I begun optimizing. I started by removing the pieces that were repeated due to equivalent rotations or mirroring, reducing the number of pieces to 2285. Then I created some methods to evaluate the viability of reaching a solution right after inserting each piece. This means that after inserting a piece on the board the algorithm tests if there are any holes on the board that will never be filled because they’re too small to fit any left over piece this way eliminating unnecessary tests.

Even so, the algorithm takes too much time to calculate a single solution (I’m interested in getting all the possible solutions). I can’t predict how much time it will take, since the combination cutting routine makes it very hard to compute how many interactions I have eliminated.

What I want from you is some suggestions on how to reach a solution in useful time (let’s say 24 hours). I'm sure it would be possible. We have reached the moon for god sake!

All the 13 puzzle pieces:







Due to lack of time I still havent finished the programs. The algorithms I have implemented are almost done, but some tiny bug is stopping the algorithms to reach a solution. Feel free to experiment. A graphical board with animation is included.

• Recursive Implementation
• Genetic Algorithms Implementation

Good luck.

Cheers.