Osterrätsel 2025: Auswertung Ihrer Rutschpartien
Für unser Rätsel sollten Sie den Pinguin Chilly in drei Levels über die längste Route zum Ziel schubsen. Die Aufgabe war schwerer als erwartet. Die Auflösung.
(Bild: KI, Bearbeitung heise online)
- Oliver Lau
Der aus den 40-Jahre-c’t-Rätseln bekannte Pinguin Chilly trug für das Osterrätsel 2025 ein Hasenkostüm. Nicht ohne Grund, denn er sollte für den Osterhasen Eier sammeln. Anders als beim Weihnachtsrätsel 2023 war er diesmal früh dran und wollte die Zeit nutzen, um sein rutschiges Revier ausführlich zu erkunden.
Die Aufgabe war deshalb, ihn ĂĽber die Route mit den meisten ZĂĽgen von seinem Startpunkt ĂĽber alle Eier zum grĂĽnen Zielfeld zu lotsen. Um endloses Rutschen zu vermeiden, sollte der Pinguin keine doppelten Wege (Level 1 und 3) beziehungsweise an keiner Stelle ein weiteres Mal Halt machen dĂĽrfen (Level 2). Als Strecke galt dabei der Weg zwischen Start und Ende eines Rutschvorganges, als Halt dessen Ende.
Denkt man sich die Halte als Knoten eines Graphen und die Wege dazwischen als Kanten, kommt man zu einem gerichteten, zyklischen Graphen. Den Graphen fĂĽr Level 1 sehen Sie im Bild unten. Entstanden ist dieses Bild mithilfe der Graphenvisualisierungssoftware GraphViz, die eine von unserem Solver erzeugte DOT-Datei eingelesen hat. Die Beschriftungen der Kanten sind die Schubsrichtungen: L fĂĽr links, U fĂĽr hoch ("up"), R fĂĽr rechts und D fĂĽr runter ("down"). Sie sollten uns die drei ermittelten Routen als Zeichenketten zusenden.
Unser Solver
An der niedrigen Zahl von nur 21 Einsendungen ist gut zu erkennen, dass die Probleme anders als in vorangegangenen Rätseln unmöglich per Hand gelöst werden konnten, sondern fundierte Programmierkenntnisse vonnöten waren. Erwartungsgemäß hat kein Teilnehmer den Pinguin per Hand zum Ziel gebracht, auch nicht beim vergleichsweise einfachen Level 1.
Überrascht waren wir jedoch, dass die ersten Lösungen bereits in den ersten drei Tagen nach Veröffentlichung des Artikels bei uns eintrafen. Denn vor allem das Finden des längsten Wegs in Level 3, ohne Kanten mehrmals zu besuchen, ist ein NP-schweres Problem und damit eine sehr rechenintensive Angelegenheit.
Kleiner Ausflug ins Home-Office-Rechenzentrum: Unsere Brute-Force-Tiefensuche läuft vermutlich immer noch, wenn Sie diesen Artikel lesen. Auf einem viel zu langsamen Rechner mit Intel N100 rödelt unser Solver in einem Thread ununterbrochen seit dem 16. März vor sich hin (immerhin zu fast 100 Prozent von Solarstrom gespeist). Zum Glück hat er schon nach wenigen Minuten brauchbare Lösungen mit 77 Zügen ausgespuckt. Deshalb hatten wir diese Zahl auch als Minimum für eine gültige Einsendung vorgegeben. In den folgenden Tagen stieg die Zahl auf 83.
Videos by heise
