Das Pentomino-Puzzle

Auch hierbei handelt es sich um ein bekanntes Puzzle: Man setzt 5 Quadrate in allen möglichen Weisen aneinander. Es entstehen 12 Puzzle-Teile, die "Pentominos". Die Aufgabe ist es nun, mit den Pentominos bestimmte Formen zu legen, beispielsweise Rechtecke. Obwohl es beispielsweise 2339 Lösungen (plus daraus durch Drehung und Spiegelung entstehende) für das 6x10-Rechteck gibt, ist es per Hand gar nicht so einfach, überhaupt eine Lösung zu finden. Das Problem scheint also wie geschaffen für den Computer.

+---+---------------+---+-----------+-------+---+-------------------+---+-------+
|   |               |   |           |       |   |                   |   |       |
|   |   +-------+---+   +---+   +---+   +---+   +-------+-------+---+   +---+   |
|   |   |       |           |   |       |   |           |       |           |   |
|   +---+---+   +-------+   |   |   +---+   +-------+   |       +---+   +---+   |
|           |           |   |   |   |               |   |           |   |       |
+-----------------------+---+---+---+---------------+---+-----------+---+-------+

Das folgende Programm erzeugt die Pentominos (oder wenn man will auch die Hexominos, Septominos usw..) automatisch, und sucht dann nach Lösungen auf beliebigen (also auch anderen als rechteckigen) Feldern.

Es handelt sich um ein ANSI-C-Programm mit einer Text-Ausgabe, sollte also auf allen Betriebssystemen laufen und (vielleicht mit minimalen Anpassungen) mit allen C-Compilern übersetzt werden können. Es ist ziemlich stark modularisiert und kann (glaube ich) auch von Programmier-Anfängern leicht verstanden werden.

Hier die gemessenen Laufzeiten für Pentominos auf rechteckigen Feldern auf einem Pentium1 mit 166MHz:

Download: pentominos.c.gz (5KB).