Minesweeper kennt man als Zugabe auf dem PC, doch auch in Mathematik und Informatik hat es für Gesprächsstoff gesorgt. Das Stichwort lautet „NP-vollständig“.
Minesweeper ist NP-vollständig
Um das Jahr 2000 zeigte der Mathematiker Richard Kaye, so heißt es, dass die folgende Frage zu Minesweeper zu den schweren Problemen gehört, die man „NP-vollständig“ nennt.
Gegeben ist ein Brett mit Zahlen. Gibt es überhaupt eine Verteilung der Minen, die zu allen Zahlen passt?
Auch die Frage, die du beim Spielen stellst, nämlich „Ist dieses Feld sicher?“, hängt eng mit dieser Aufgabe zusammen.
Was NP-vollständig heißt
Einfach gesagt hat ein NP-vollständiges Problem diese Eigenschaften.
- Eine Antwort zu prüfen ist leicht: Wenn dir jemand eine Minenverteilung zeigt, kannst du schnell nachprüfen, ob sie zu allen Zahlen passt.
- Eine Antwort zu finden ist (vermutlich) schwer: Wächst das Brett, wächst die Zahl der Möglichkeiten sprunghaft. Bisher kennt man keine Methode, die für jedes Brett schnell eine Antwort findet.
Außerdem weiß man, dass sich NP-vollständige Probleme ineinander umformen lassen. Fände jemand für nur eines davon eine Methode, die immer schnell funktioniert, ließen sich alle anderen NP-vollständigen Probleme ebenfalls schnell lösen. Ob es so eine schnelle Methode gibt, ist die berühmte ungelöste Frage „P ungleich NP?“. Auf ihre Lösung ist ein Preis von einer Million Dollar ausgesetzt.
Die Zahl der Verteilungen explodiert
Die Prüfung ist aufwendig, weil die Zahl der Möglichkeiten riesig wird.
- 8 Minen auf einem 9×7-Brett zu verteilen heißt, 8 von 63 Feldern auszuwählen. Das sind etwa 3,9 Milliarden Möglichkeiten.
- 75 Minen auf einem 26×15-Brett zu verteilen heißt, 75 von 390 Feldern auszuwählen. Das ist eine Zahl mit mehr als 80 Stellen.
Beim Spielen musst du natürlich nicht alles durchprobieren. Felder ohne angrenzende Zahl kannst du zusammen betrachten, und in vielen Situationen reicht der Blick auf eine oder zwei Zahlen. Trotzdem kann es schwierig werden, sicher zu entscheiden, wenn sich Zahlen stark verflechten.
Die App wählt nur Bretter, die man logisch lösen kann
Beim Erzeugen eines Bretts prüft die App Minesweeper, ob es sich vom Anfang bis zum Ende allein mit diesen drei Regeln lösen lässt, die auch Menschen benutzen.
- Was sich aus einer einzelnen Zahl ergibt
- Was sich aus der Kombination von zwei Zahlen ergibt
- Was sich aus der Zahl der Restminen auf dem ganzen Brett ergibt
Jede Regel betrachtet nur einen kleinen Bereich und lässt sich schnell prüfen. Bretter, die mit diesen dreien nicht lösbar sind, werden neu erzeugt, indem Minen verschoben werden. Deshalb kommst du immer bis zum Ende, ohne alle Verteilungen durchgehen zu müssen.
Die Bretter, die du in den Artikeln dieser Seite spielen kannst, entstehen nach demselben Prinzip. Als wir am PC gemessen haben, wie lange es dauert, ein Brett in der Größe von ★5 zu erzeugen, waren es im Schnitt wenige Millisekunden pro Brett.
Rätsel und Mathematik
Auch viele andere Bleistifträtsel wie Sudoku sind in ihrer allgemeinen Form mit beliebig großen Brettern NP-vollständig. Rätsel, die Menschen gern lösen, sind oft so gebaut, dass man sie Schritt für Schritt per Logik lösen kann, ohne alles durchzuprobieren. Auch die Bretter der App Minesweeper, bei denen man nie raten muss, gehören dazu.
Zur Wahrscheinlichkeitsrechnung steht mehr unter Wahrscheinlichkeiten beim Minesweeper.
