Pentaminos

The pentaminos are the puzzle's pieces represented on the beside picture. They are the 12 different pieces that you can obtain joining 5 identical cubes side by side.
The rule of the game is to reconstitute a given shape. Most of the time, you have to put them into a 8 x 8 array, in which 4 cases must stay empty. Here are some examples:

but there are many others.
I decided on day to find the number of solutions, for a given array. I realised a little program to do it, first in C, then in Objective Caml later. It is a backtracking algorithm, which stops whenever an area to fill has a surface which is not a multiple of 5.

Some answers computed by the program.

You can download:

The Objective Caml source code
This program determines the symmetries of the problem and uses them to reduce the search space. Thanks to Judicaël Courant for his help on this particular problem.
An equivalent C program, only 25% faster (without optimized compilation)
Here the problem and its symmetries are manually given in the source.

Variant

A variant consists in arranging the 12 pentaminos in a rectangle. Here are the number of solutions (up to the 4 symmetries):

3 x 20 : 2 solutions
4 x 15 : 368 solutions
5 x 12 : 1010 solutions
6 x 10 : 2339 solutions

The Caml program

Jean-Christophe Filliâtre (formatted with yamlpp).