Es ist erwiesen, dass ein Standard-Sudoku-Rätsel mindestens 17 Hinweise haben muss, um eine eindeutige Lösung zu haben.
Sudoku-Regeln:
Geben Sie die Zahlen 1–9 in jede Zeile, Spalte und jedes 3x3-Unterraster in einem 9x9-Raster ein.
Jede Zahl kann in jeder Zeile, Spalte und jedem 3x3-Untergitter nur einmal vorkommen.
Füllen Sie die Leerzeichen mit den Zahlen 1–9 aus, sodass jede Zeile, jede Spalte und jedes 3x3-Unterraster alle Zahlen 1–9 enthält.
Sudoku ist ein auf Logik basierendes Zahlenrätsel. Das Ziel besteht darin, ein 9x9-Raster mit den Zahlen 1-9 zu füllen, sodass jede Zeile, jede Spalte und jedes 3x3-Untergitter alle neun Zahlen genau einmal enthält.
Im Jahr 2009 bewiesen Gary McGuire und sein Team, dass jedes Sudoku-Rätsel mit 16 Hinweisen mindestens zwei Lösungen haben muss. Sie erreichten dies mithilfe einer Technik namens „tote Muster“.
Ein totes Muster ist eine Sudoku-Konfiguration mit zwei oder mehr möglichen Lösungen. McGuire und sein Team fanden heraus, dass jedes Sudoku-Rätsel mit 16 Hinweisen mindestens ein totes Muster enthalten muss. Daher müssen diese Rätsel mindestens zwei Lösungen haben.
Dieses Ergebnis hat mehrere Implikationen. Erstens bedeutet es, dass es kein Sudoku-Rätsel mit 16 Hinweisen und einer eindeutigen Lösung gibt. Zweitens bedeutet es, dass jedes Sudoku-Rätsel mit 16 Hinweisen auf verschiedene Arten gelöst werden kann. Drittens bedeutet es, dass es unendlich viele Sudoku-Rätsel mit 16 Hinweisen gibt.
Hier ist eine technischere Erklärung des Beweises, dass Sudoku-Rätsel mindestens 17 Hinweise haben müssen, um eine eindeutige Lösung zu haben:
Der Beweis beginnt mit der Betrachtung eines Sudoku-Rätsels mit 16 Hinweisen. Wir können uns dieses Rätsel als eine Reihe von Einschränkungen für die Zahlen vorstellen, die in die leeren Felder eingefügt werden können.
Anschließend können wir mithilfe einer Technik namens „Backtracking“ versuchen, eine Lösung für das Rätsel zu finden. Backtracking ist ein rekursiver Algorithmus, der alle möglichen Zahlenkombinationen in den leeren Feldern ausprobiert, bis eine Lösung gefunden wird.
Wenn es eine eindeutige Lösung für das Rätsel gibt, wird man sie schließlich durch Zurückverfolgen finden. Wenn es jedoch mehrere Lösungen gibt, kann es sein, dass durch Zurückverfolgen nie eine Lösung gefunden wird.
McGuire und sein Team verwendeten Backtracking, um zu zeigen, dass es bei einem Sudoku-Rätsel mit 16 Hinweisen und einer eindeutigen Lösung eine Möglichkeit geben muss, den Backtracking-Algorithmus so zu starten, dass er immer die Lösung findet.
Sie zeigten dann, dass dies nicht möglich ist. Dazu konstruierten sie eine Reihe von 16 Hinweisen, die zu einem toten Muster führen. Dieses tote Muster bedeutet, dass es zwei mögliche Lösungen für das Rätsel gibt und es keine Möglichkeit gibt, den Backtracking-Algorithmus so zu starten, dass er immer die gleiche Lösung findet.
Dieses Ergebnis zeigt, dass jedes Sudoku-Rätsel mit 16 Hinweisen mindestens zwei Lösungen haben muss.