Katzenpuzzle
Schwierige und leichte Probleme – das Katzenpuzzle sieht kinderleicht aus. Löst es selbst und findet heraus, warum es für Computer gar nicht so leicht lösbar ist.
Wir nehmen oft an, das Computer eigentlich alles lösen können. Doch es gibt sehr viele Probleme, für die es sehr lange dauert eine Lösung zu finden. Es gibt sogar einige, die so schwierig sind, dass es hunderte oder tausende Jahre dauern würde, sie zu lösen.
Das Katzenpuzzle gehört zu besonders schwer zu lösenden.
Aber keine Sorge, ihr werdet sicher die Lösung finden – vielleicht sogar schneller als der Computer.
Ihr könnt es hier herunterladen:
Katzenpuzzle zum Ausdrucken herunterladen
Alle unsere Materialien stehen unter einer CC-BY-SA-Lizenz.
Das Quanten 1×1 macht die wichtigsten Erkenntnisse der Quantenwelt einfach begreiflich. Mit Hilfe von leicht verständlichen Videos und den neuen Tüftelboxen bekommt ihr ein Grundverständnis für die Quantentechnologien der zweiten Generation.
Wir haben über 20 Quanten-Expert*innen aus unterschiedlichen Wissenschaftsbereichen besucht. Die Gespräche könnt ihr auf den verschiedenen Themenseiten entdecken!
Katzenpuzzle Rätsel
⏰ Dauer ca. 20 – 60 min
Vorbereitung und Materialien
✂️ Schere
🖨️ Drucker
Druckt das PDF farbig aus.
Schneidet die Puzzleteile aus.
Super, jetzt habt ihr 9 Puzzleteile und es kann losgehen.
Tipp: Ihr könnt auch festeres Papier nutzen, dann ist das Puzzle griffiger.
Puzzeln
Rettet die Katzen!
Könnt ihr helfen, die Katzen richtig zusammenzusetzen? Jede Katze benötigt einen Kopf und einen Körper, aber beide müssen die gleiche Farbe haben.
Achtet darauf, dass das Puzzle ein 3×3 Quadrat ergibt.
Ganz schön kniffelig! Wundert euch nicht, wenn es etwas länger dauert. Das Spiel sieht viel einfacher aus, als es ist. Man benötigt Geduld und auch etwas Glück.
Lösung
Wir kennen bereits zwei Lösungen.
Findest du noch eine weitere?
Lösung
Wir kennen bereits zwei Lösungen.
Findest du noch eine weitere?
Was hat das Puzzle mit Computern,
Algorithmen und Quanten zu tun?
Wenn euch jemand ein fertiges Puzzle zeigt, könnt ihr in Sekundenschnelle überprüfen, ob das Ergebnis richtig ist. Aber die richtige Lösung zu finden, ist sehr viel komplizierter. Denn es gibt eine riesige Anzahl von Möglichkeiten, die Puzzleteile zu platzieren. Es gehört zu den schweren Problemen.
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.
Stell dir 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.
Die Anzahl der Möglichkeiten
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 übrigens „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, 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
Damit wir die Formel auch für kleinere und größere Puzzle benutzen können, können wir die Formel etwas umschreiben. Unser Puzzle hat neun Teile, da es quadratisch ist und die Seitenlänge drei ist. Wenn wir als Seitenlänge nun statt der 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
Könnt ihr die Anzahl der Möglichkeiten berechnen? Benutze dafür gerne einen Taschenrechner.
K(n) = (n⋅n)!⋅4(n⋅n)
Mögliche Lösungen
Seitenlänge 2, n=2
Seitenlänge 3, n=3
Seitenlänge 4, n=4
Seitenlänge 5, n=5
Wie schnell ist ein (klassischer) Computer?
Ein Computer kann rasend schnell die Puzzleteile hinlegen und die Lösung überprüfen. Wenn wir annehmen, dass ein Computer etwa eine Million Möglichkeiten in der Sekunde ausprobieren kann, benötigt er für ein leichteres 2×2 Puzzle weniger als eine Sekunde!
Lönnt ihr ausrechnen wie lange er dann für das 3×3 Katzenpuzzle benötigt oder auch für größere? Zum Beispiel 4×4, 5×5, 6×6, 7×7 …?
t(n) = (n⋅n)!⋅4(n⋅n) / 1000000
Tipp: Ihr müsst die Sekunden vielleicht auch in Minuten, Stunden und so weiter umrechnen.
Mögliche Lösungen
Seitenlänge 2, n=2
Seitenlänge 3, n=3
Seitenlänge 4, n=4
Seitenlänge 5, n=5
Eine 💰 Million Preisgeld
Wow, habt ihr euch die Zahlen notiert und verglichen?
Schon beim 5×5 Puzzle müssten wir 169 Millionen Jahre auf das Ergebnis warten. Selbst wenn jemand einen Supercomputer hat, der eintausend mal so schnell ist wie unser Computer, niemand hat Zeit so lange zu warten.
Deswegen wird das Katzenpuzzle als „schweres Problem“ bezeichnet. Für ganz kleine Datenmengen (unsere Puzzleteile) lässt es sich noch lösen, aber wenn die Seitenlänge nur etwas größer wird, ist es schnell so kompliziert, dass wir so lange auf das Ergebnis warten müssten, dass es eigentlich nicht lösbar ist. Also mit doppelt so vielen Puzzleteilen benötigen wir nicht nur doppelt so lange, sondern sehr viel länger.
Man sagt, es „skaliert nicht“.
Wenn du dir aber einen Algorithmus überlegen kannst, der für die doppelte Anzahl an Puzzleteilen nicht wesentlich länger als doppelt so lange benötigt, bekommst du 1 Million Dollar. Denn damit wäre das P-NP-Problem gelöst. Es ist eines der sieben Millennium Probleme, die das Clay Mathematics Institute im Jahr 2000 aufgezählt hat, und für die Lösung jeweils 1 Million Dollar bezahlt.
Alternativ darf man übrigens auch mathematisch beweisen, dass es keine Lösung geben kann.
Quantencomputer
Wie oben gesagt, gibt es viele solcher schweren Probleme. Gerade in der Forschung treffen Wissenschaftler immer wieder auf sie. Aber eine Lösung würde uns auch in unserem Alltag helfen.
Gerade wird ganz intensiv an Quantencomputern geforscht, denn sie können wesentlich schneller rechnen als unsere klassischen Computer. Deswegen hat die Bundesregierung 2021 zwei Milliarden für die Forschung an Quantencomputern zur Verfügung gestellt.
Ein Quantencomputer löst leider das Millennium Problem auch nicht. Zumindest existiert auch hier noch kein passender Algorithmus.
Er ist trotzdem wesentlich schnell, denn er hat einen sogenannten „quadratischen Speedup“. Übersetzt bedeutet das, er überprüft nur die Wurzel aller Möglichkeiten und weiß trotzdem die richtige Lösung.
Um alle Möglichkeiten beim 3×3 Puzzle zu testen, benötigt er dann statt über einem Tag nur noch Sekunden.
Bisher wird aber noch an Quantencomputern geforscht. Es wurde gezeigt, dass sie prinzipiell funktionieren, aber um wirklich gut Probleme zu lösen, sind sie noch nicht gut genug.
Wenn ihr mehr über Quanten, Quantencomputer und andere Quantentechnologien erfahren wollt, besucht unser Quanten 1×1!
Weitere Infos
Ihr findet viele Informationen zu Quantentechnologien und Quantencomputer mit spannenden Interviews, Animationen, Workshops und Tüftelboxen in unserem Quanten 1×1.
Auch in der Broschüre „QBTS NEWS“ gibt es das Katzenpuzzle als Affenpuzzle und mehr Wissen zu Quantentechnologien für Lehrkräfte und Schüler*innen
Falls ihr keine ✂️ Scheere zur Hand habt, könnt ihr auch das Affenpuzzle am Computer auf inf-schule spielen. Dort gibt es eine digitale Version, viele gute Informationen zu Komplexität von Algorithmen und auch schwierigere und leichtere Puzzle (mit Seitenlänge 2, 3, 4 und 5).
Dr. Gero Scholz hat ein Programm geschrieben, u× das Puzzle mit dem Computer zu lösen und getestet, wie lange er benötigt. Dabei konnte er den einfachen Algorithmus noch verbessern. Schließlich würden wir als Menschen auch nie alle neun Teile auslegen und dann erst testen, ob es eine Lösung ist, wenn wir bereits sehen, dass die ersten zwei Puzzleteile nicht zusammenpassen.
Sein Algorithmus konnte das 5×5 Puzzle sogar in einer Minute lösen, um. Aber schon für das Nächstgrößere müsste er mehrere Monate warten.
Das Katzenpuzzle kommt als Beispiel für schwere Probleme auch in Büchern vor. Dort ist es häufig ein Affenpuzzle.
„Das Affenpuzzle und weitere bad news aus der Computerwelt“ von David Harel
„Abenteuer Informatik: IT zum Anfassen für alle von 9 bis 99“ von Jens Gallenbacher
