Wenn euch jemand ein fertiges Katzenpuzzle zeigt, könnt ihr in Sekundenschnelle überprüfen, ob das Ergebnis richtig ist.

Die richtige Lösung zu finden, ist jedoch sehr viel komplizierter. Denn es gibt eine riesige Anzahl von Möglichkeiten die Puzzleteile zu platzieren. Das Katzenpuzzle gehört zu den schweren Problemen.

Das Überprüfen einer gefundenen Lösung des Puzzles ist an sich äußerst einfach und effizient. Die eigentliche Suche nach der Lösung hingegen ist sehr komplex!
 Ein Algorithmus zur Lösung
Ein einfacher Algorithmus würde alle Möglichkeiten einfach durchprobieren. Der Computer würde alle neun Puzzleteile platzieren und dann prüfen, ob die Anordnung richtig ist. Ist die Anordnung richtig, ist er fertig. Ist sie falsch, probiert er eine andere Anordnung aus.
Stellt euch ein leeres Puzzle vor – also ein Quadrat, in das die Puzzleteile gelegt werden sollen:

  • Für das erste Puzzle-Teil gibt es also neun Möglichkeiten, wo es hingelegt werden kann.

  • Für das zweite Teil gibt es nur noch acht freie Plätze. Denn ein Puzzle-Teil liegt ja bereits dort.

  • Für das dritte Teil gibt es noch sieben freie Plätze. Und so weiter.

  • Für das achte Teil nur noch zwei, denn es sind bereits sieben platziert, somit sind nur noch zwei Stellen frei.

  • Und beim neunten Teil gibt es dann nur noch eine Möglichkeit.

So wird auf jeden Fall eine Lösung gefunden! Die Anzahl an Möglichkeiten können wir berechnen.

 Anordnung der Puzzleteile

Erstes Teil: 9 Möglichkeiten [multiplizieren mit] zweites Teil: 8 Möglichkeiten [multiplizieren mit] drittes Teil: 7 Möglichkeiten [multiplizieren mit] … neunten Teil: 1 Möglichkeiten.

= 9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1 = 9! Möglichkeiten.

„9⋅8⋅…⋅1“ kann man auch kürzer schreiben als „9!“ (gesprochen: neun Fakultät).

Alle Möglichkeiten der Anordnung ohne Wiederholung nennt man in der Kombinatorik „Permutation ohne Wiederholung“.
 Rotation der Puzzleteile

Zusätzlich müssen wir beachten, dass die Puzzleteile nicht richtig gedreht sind. Jedes Puzzleteil hat vier Seiten, kann also auch in vier Richtungen gedreht werden. Jedes Puzzlestück in vier Richtungen gedreht ergibt also:

4⋅4⋅4⋅4⋅4⋅4⋅4⋅4⋅4 = 49.

Die ganze Formel

Zusammengesetzt ergibt sich also für unser Katzenpuzzle (3×3) folgende Formel:

9! ⋅ 49 = Anzahl der Möglichkeiten

Um die Formel auch für kleinere und größere Puzzle zu benutzen, können wir sie etwas umschreiben. Unser Puzzle hat neun Teile, da es quadratisch ist und die Seitenlänge drei ist. Wenn wir anstelle der festen Seitenlänge von drei eine Variable nutzen, die wir „n“ nennen, ergibt sich:

K(n) = (n⋅n)!⋅4(n⋅n)

Wenn wir nun die Anzahl an Möglichkeiten für egal welche Puzzlegröße wissen möchten, können wir einfach alle „n“ in der Formel mit der Seitenlänge ersetzten

Und nun in Zahlen

Aufgabe 

Könnt ihr die Anzahl der Möglichkeiten berechnen? Benutzt dafür gerne einen Taschenrechner. 

K(n) = (n⋅n)!⋅4(n⋅n)

Klickt auf die anderen Tabs, um euch mögliche Lösungen anzeigen zu lassen.

6144
95.126.814.720
89.862.698.310.039.502.848.000
≈ 1,746 ⋅ 1040