»Lights Out« in Deus Ex

Code & Zahlen

Im Computerspiel Deus Ex: Mankind Divided habe ich ein Lights Out Puzzle gefunden. Ich war zu faul zu raten, also schrieb ich ein Programm um es zu lösen.

Das Lights Out ist ein klassisches Rätsel oder Minispiel. Man hat eine Menge beleuchtete Taster. Drückt man einen, so schaltet sich das Licht von dem Schalter und der vier direkten Nachbarn um. Ziel des Spiels ist es so lange die Schalter zu drücken, bis alle Lichter aus sind.

In Deus Ex hatten sie es anders herum, man sollte alle Schalter einschalten. Ich habe erstmal planlos gedrückt, und hatten dann diesen Zustand.

Ich habe weiter herumgedrückt, konnte es aber nicht lösen. Am Ende hatte ich es auf das hier reduziert.

An sich ist das Spiel relativ limitiert. Es gibt 9 Schalter mit je zwei Zuständen. Somit ergeben sich 2⁹ = 512 Zustände mit klaren Übergängen dazwischen. Ich habe also in Python-Programm geschrieben, das die Lösungen erzeugt. Das Programm nutzt die igraph-Bibliothek um einen Graph aller Zustände aufzuspannen und dann den kürzesten Weg zwischen meinem aktuellen Stand und der Lösung auszurechnen:

import copy
import itertools
from typing import Iterator

import igraph as ig


State = list[list[bool]]


def iter_transitions(state: State) -> Iterator[State]:
    for row in range(3):
        for col in range(3):
            new_state = copy.deepcopy(state)
            for r, c in [
                (row, col),
                (row - 1, col),
                (row + 1, col),
                (row, col - 1),
                (row, col + 1),
            ]:
                if 0 <= r < 3 and 0 <= c < 3:
                    new_state[r][c] = not new_state[r][c]
            yield new_state


def state_to_string(state: State) -> str:
    return "|".join("".join("#" if cell else " " for cell in row) for row in state)


def main():
    states = [
        [[s1, s2, s3], [s4, s5, s6], [s7, s8, s9]]
        for s1, s2, s3, s4, s5, s6, s7, s8, s9 in itertools.product(
            [True, False], repeat=9
        )
    ]

    states_str = [state_to_string(state) for state in states]

    transitions = {
        state_to_string(state): [
            state_to_string(new_state) for new_state in iter_transitions(state)
        ]
        for state in states
    }

    print(len(states))

    g = ig.Graph(
        len(states),
        [
            (states_str.index(source), states_str.index(target))
            for source, targets in transitions.items()
            for target in targets
        ],
    )

    path = g.get_shortest_paths(
        states_str.index("   |   |  #"),
        states_str.index("###|###|###"),
    )
    print(path)
    for elem in path[0]:
        print("---")
        print(states_str[elem].replace("|", "\n"))
        print("---")
        print()


if __name__ == "__main__":
    main()

Aus der Ausgabe kann man dann die Zwischenzustände entnehmen.

---


  #
---

---
###
 # 
  #
---

---
# #
# #
 ##
---

---
 ##
  #
 ##
---

---
###
###
###
---

Es braucht also diese vier Schritte zum Umschalten:

---
31
42

---

Die Reihenfolge der Schritte ist dabei sogar egal, man muss einfach nur diese Schalter drücken.

Wahrscheinlich habe ich es mir am Ende schwerer gemacht, als wenn ich einfach noch ein bisschen probiert hätte. Aber irgendwie ist ein Programm mit einem Graphen zu schreiben für mich ein klarerer Lösungsweg als herumzuprobieren.