Puzzle lösen

musicman

Hi,
ich bin gerade dran, Programm zu schreiben, das ein Puzzle löst, welches so ähnlich ist wie das aus c't 7/03 (Holzklötze zu einem Würfel zusammensetzen).

Allerdings bin ich mir nicht so sicher, ob das auch in vernünftiger Zeit lösbar ist (ich vertrau *zum Glück?* nicht so auf meine Kombinatorikkenntnisse).

Doch nun zum Aufbau:
Das Puzzle besteht aus einem

5 x 5 x 5 großen Würfel

der mit folgenden 25 gleichen Teilen aufgefüllt werden soll:

####
 #

Die Teile sind 4 Einheiten lang, und an 2. Stelle 2 Einheiten breit (so wie es die Grafik versucht zu zeigen). Sie sehen alle gleich aus, und können in alle Richtungen gedreht werden. Im Endeffekt sollte sich der Würfel damit komplett ohne Löcher füllen lassen.

Was mir jetzt noch fehlt ist so eine ungefähre Aufwandsabschätzung für die Rechnung, da ich auf ca. 10^77 verschiedene Möglichkeiten gekommen bin (hoffentlich falsch!) die Teile zu platzieren.

Falls jemand sicherer in Kombinatorik ist,

Vielen Dank

volkard

musicman schrieb:

da ich auf ca. 10^77 verschiedene Möglichkeiten gekommen bin (hoffentlich falsch!) die Teile zu platzieren.
Falls jemand sicherer in Kombinatorik ist,

lös mal schnell das 8-damen-problem und brauche nicht in der größenordnung von 8^8 versuchen.
mit backtracking solltest du bei wenigen dutzend versuchen sein.

wende den gleichen trick auf dein puzzle an. das hat mein prog vom c't-puzzle afair von 70 tagen auf 9 stunden runtergeholt.

musicman

Backtracking ist schon klar, aber den Würfel kann ich nicht in kleinere Teile zerlegen, um das Problem einfacher zu machen, da das von der Logik her nicht funktioniert. Die Teile können in keine kleineren Formen gebracht werden, die ich dann noch zu einem 5x5x5 Würfel zusammensetzen kann.

Jester

Jo, aber da Deine Formen für die Puzzle-Steine alle gleich sind kannst Du unter umständen sehr leicht rausfinden, ob sich überhaupt noch alles füllen läßt.
Insbesondere Löcher, die nicht mehr allzuviele freie Nachbarn haben sind so Kandidaten, wenns keine Möglichkeit mehr gibt das zu stopfen kannste gleich abbrechen.
Besonders Rand und Ecklöcher sind solche Prüfkandidaten, weil es bei denen sowieso nur eingeschränkte Möglichkeiten gibt sie zu belegen.

MfG Jester