Lichter aus

„Lights Out“ ist ein Logikrätsel, das auf einem Raster aus Lichtern gespielt wird, von denen jedes entweder an oder aus sein kann. Durch Drücken eines beliebigen Lichts wird dieses sowie alle orthogonal benachbarten Lichter (oben, unten, links, rechts) umgeschaltet. Das Ziel ist es, alle Lichter auszuschalten. Das Rätsel ist tückisch schwierig, da jeder Zug mehrere Lichter betrifft und das Ausschalten eines Lichts dazu führen kann, dass andere eingeschaltet werden. Die klassische Version verwendet ein 5×5-Raster, aber das Konzept funktioniert bei jeder Rastergröße.

Regeln

1. Das Spiel beginnt mit einem Raster aus Lichtern, von denen einige leuchten und andere nicht (oder in der klassischen Version leuchten alle).
2. Durch Antippen eines Lichts wird dessen Zustand umgekehrt (leuchtet → nicht leuchtet, nicht leuchtet → leuchtet).
3. Durch das Antippen eines Lichts werden auch alle direkt benachbarten Lichter umgeschaltet (oben, unten, links, rechts – keine Diagonalen).
4. Das Ziel ist es, alle Lichter auszuschalten.
5. Wird dasselbe Licht zweimal angetippt, hebt sich die Aktion auf, sodass jedes Licht nur einmal oder gar nicht angetippt werden muss.

Strategien

• Die Reihenfolge spielt keine Rolle: Der Endzustand hängt nur davon ab, welche Lichter gedrückt wurden, nicht von der Reihenfolge. Das bedeutet, dass du deine Lösung planen kannst, ohne dir Gedanken über die Reihenfolge zu machen.
• Jedes Licht höchstens einmal gedrückt: Da das zweimalige Drücken eines Lichts dieses (und seine Nachbarn) in den ursprünglichen Zustand zurückversetzt, wird bei einer optimalen Lösung dasselbe Licht nie mehr als einmal gedrückt.
• Lichtjagd (von oben nach unten): Beginne in der obersten Reihe. Drücke bei jeder leuchtenden Zelle in einer Reihe auf die direkt darunter liegende Zelle, um sie auszuschalten. Dadurch werden die Lichter nach unten „verjagt“. Nachdem alle Reihen bearbeitet wurden, darf nur noch in der untersten Reihe Licht leuchten.
• Wrap-Around-Korrektur: Wenn nach dem „Light Chasing“ in der untersten Reihe noch Lichter leuchten, müssen bestimmte Muster in der obersten Reihe umgeschaltet werden, bevor erneut „Light Chasing“ durchgeführt wird. Es gibt bekannte Nachschlagetabellen, aus denen hervorgeht, welche Tastenbetätigungen in der obersten Reihe jedes Muster in der untersten Reihe beheben.
• Ansatz der linearen Algebra: Das Rätsel lässt sich als ein System linearer Gleichungen über GF(2) (dem Körper mit den zwei Elementen 0 und 1) modellieren. Jeder Tastendruck ist ein Vektor, und die Lösung ist eine Kombination von Vektoren, die den Zielzustand erzeugt. Nicht alle Ausgangskonfigurationen sind lösbar.
• Inaktive Muster: Manche Tastenkombinationen lassen das Spielfeld unverändert. Das Verständnis dieser „Nullmuster“ hilft dabei, festzustellen, ob ein Rätsel eine Lösung hat, und alternative Lösungen zu finden.

„Lights Out“ wurde ursprünglich 1995 von Tiger Electronics als elektronisches Handheld-Spiel veröffentlicht. Das Gerät verfügte über ein 5×5-Raster aus hintergrundbeleuchteten Tasten und entwickelte sich zu einem beliebten Spielzeug und Rätsel. Das Spiel präsentierte den Spielern zufällige Startkonfigurationen und forderte sie heraus, alle Lichter auszuschalten.

Das zugrunde liegende mathematische Konzept ist jedoch bereits Jahrzehnte älter als das kommerzielle Produkt. Die Umschaltmechanik – bei der das Drücken eines Elements Auswirkungen auf seine Nachbarn hat – wurde in der Mathematik bereits in den 1960er Jahren im Zusammenhang mit Sigma-Automaten und zellulären Automaten untersucht. Die mathematische Theorie hinter dem Rätsel umfasst lineare Algebra über endlichen Körpern, insbesondere GF(2), wobei die Addition der XOR-Operation entspricht.

Das Rätsel fand bei Mathematikern und Informatikern große Beachtung. Im Jahr 1998 veröffentlichten Marlow Anderson und Todd Feil eine gründliche mathematische Analyse, die zeigte, dass genau 4 der 2^25 (etwa 33,5 Millionen) möglichen Startkonfigurationen des 5×5-Rasters unlösbar sind. Sie wiesen zudem nach, dass die lösbaren Konfigurationen immer in höchstens 15 Zügen gelöst werden können. Die Analyse nutzt Eigenwerte der Adjazenzmatrix über GF(2) und verbindet das Rätsel auf elegante Weise mit der Graphentheorie und der linearen Algebra.

Tiger Electronics brachte eine Fortsetzung namens „Lights Out 2000“ mit einem 6×6-Raster auf den Markt, und das Konzept wurde in Videospielen vielfach adaptiert, wo es als Rätselmechanik in Abenteuerspielen, Rollenspielen und Rätselsammlungen auftaucht. Zu den Varianten gehören hexagonale Raster, toroidale (sich umlaufende) Raster sowie Versionen mit mehr als zwei Lichtzuständen. Das Rätsel ist nach wie vor ein fester Bestandteil der Freizeitmathematik und wird häufig in Universitätskursen verwendet, um Anwendungen der linearen Algebra zu veranschaulichen.