Sudoku
Copyright © 2019 Jiri Kriz, www.nosco.ch

Die Sudoku Regel

Das Ziel des Sudoku Spiels ist, ein 9x9 Gitter mit den Zahlen 1 bis 9 zu füllen, sodass keine Zeile, keine Kolonne und keiner 3x3 Block doppelte Zahlen enthält. In anderen Worten, alle diese Regionen müssen alle Zahlen 1 bis 9 enthalten.

Lösung von Sudoku Rätseln

Sudoku Rätsel haben einige Zahlen vordefiniert und die Aufgabe besteht darin, das Gitter gemäss der Sudoku Regel vollständig auszufüllen.

Für eine leere Zelle können Sie mental alle Zahlen 1 bis 9 probieren. Die Zahlen, die man potentiell einsetzen kann ohne die Sudoku Regel zu verletzen, heissen Kandidaten. Wenn nur ein Kandidat möglich ist, so ist er der Lösungswert für diese Zelle. Diese einfachste Lösungsstrategie heisst natürlicherweise (Nackter) Single.

Sobald eine Zahl in eine Zelle eingetragen wird, so kann sie von den Kandidaten aller leeren Zellen in den zugehörigen drei Regionen (Zeile, Kolonne, Block) entfernt werden. Während des Lösungsprozesses sinkt also die Zahl der verbleibenden Kandidaten ständig. Mein Sudoku Spiel führt die Elimination der Kandidaten automatisch aus und zeigt die verbleibenden Kandidaten auf Wunsch an.

Zusätzlich zur Regel des Nackten Singles gibt es viele anderen logischen Regeln. In der folgenden Erklärung steht der Begriff Region für beliebige Zeilen, Kolonnen und 3x3 Blöcke. Jede Region muss schliesslich alle Zahlen 1 bis 9 enthalten.

Lösungsstrategien

Nackte Singles

Wenn eine Zelle nur einen Kandidaten enthält, dann muss dieser Kandidat der Lösungswert sein.

Beispiel:
Die Zelle R4C2 enthält nur einen Kandidaten (2). Der Wert von R4C2 muss also 2 sein.

Versteckte Singles

Wenn ein Kandidat nur in einer Zelle einer Region enthalten ist, dann ist dieser Kandidat die Lösung für diese Zelle.

Beispiel:
In der Reihe 1 (gelb) erscheint der Kandidat 9 nur in der Zelle R1C3 (grün). Also muss der Wert von R1C3 gleich 9 sein.

Schnitte Block/Reihe oder Block/Kolonne (oder blockierte Kandidaten)

Reihe/Block
Wenn in einer Reihe ein Kandidat nur in einem Block erscheint, dann wird dieser Kandidat sicher dort platziert und kann darum aus den anderen Reihen des Blocks entfernt werden.

Beispiel:
Die Reihe 2 (gelb) enthält den Kandidaten 2 nur innerhalb des oberen linken Blocks. Also 2 muss dort sein (grüne Zellen) und kann darum nicht im Rest des Blocks sein (rot). Der Kandidat 2 kann in den roten Zellen eliminiert werden.

Block/Reihe
Wenn ein Block einen Kandidaten nur in einer Reihe hat, dann wird dieser Kandidat irgendwo dort platziert und kann darum aus dem Rest der Reihe entfernt werden.

Beispiel:
Der obere rechte Block enthält den Kandidaten 9 nur in der Reihe 1. 9 wird also in einer der Zellen R1C8, R1C9 platziert und kann aus dem Rest der Reihe 1 eliminiert werden, d.h. von der Zelle R1C2 (rot).

Block/Kolonne und Kolonne/Block
Analoge Regeln gelten für den Schnitt von Blöcken und Kolonnen. Zum Beispiel, die Kolonne C7 hat den Kandidaten 7 nur im oberen rechten Block. Also, 7 wird dort entweder in R1C7 oder in R3C7 gesetzt, und kann somit von R1C9 gestrichen werden.

Nackte Paare

Wenn eine Region 2 Zellen enthält, die zusammen 2 Kandidaten haben, dann werden diese Zellen ihre Kandidaten konsumieren, und somit können diese Kandidaten von den übrigen Zellen der Region eliminiert werden.

Beispiel:
In der Reihe 6 erscheinen die Kandidaten 2 und 9 nur in den Zellen R6C1 und R6C6 (grün). Diese zwei Zellen werden zusammen beide Kandidaten konsumieren. Die Kandidaten 2, 9 können also von anderen Zellen der Reihe, d.h. von R6C2, R6C3 (rot) entfernt werden.

Nackte Dreier

Wenn eine Region 3 Zellen enthält, die zusammen 3 Kandidaten haben, dann werden diese Zellen ihre Kandidaten konsumieren, und diese Kandidaten können von den verbleibenden Zellen der Region entfernt werden. Beachten Sie, dass die einzelnen Zellen weniger als 3 Kandidaten haben können.

Beispiel:
Im unteren rechten Block erscheinen die Kandidaten 4, 8, 9 nur in den 3 Zellen R7C9, R8C7, R9C9 (grün). Diese 3 Zellen zusammen werden alle 3 Kandidaten konsumieren. Diese Kandidaten 4, 8, 9 können also von den anderen Zellen des Blocks, d.h. von R7C7, R7C8, R9C8 (rot) entfernt werden.

Nackte Tupel

Die Regeln Nackte Singles, Nackte Paare und Nackte Dreier sind alle ein Spezialfall der allgemeinen Regel Nackte Tupel: Wenn N Zellen in einer Region zusammen genau N Kandidaten enthalten, dann werden sie diese Kandidaten konsumieren. Diese Kandidaten können also von den anderen Zellen dieser Region entfernt werden. Im Falle N=4 heisst die Regel Nackte Vierer.

Versteckte Paare

Nehmen wir an, dass 2 Kandidaten nur in 2 Zellen einer Region erscheinen. Weil diese 2 Zellen zusammen die 2 Kandidaten konsumieren werden, können alle übrigen Kandidaten in diesen 2 Zellen entfernt werden.

Beispiel:
Im linken mittleren Block (gelb) erscheinen die Kandidaten 3 und 7 nur in den 2 Zellen R4C1 und R6C1 (grün). Also können die übrigen Kandidaten 2, 5, 8 aus diesen Zellen (R4C1 und R6C1) entfernt werden.

Versteckte Dreier

Nehmen wir an, dass 3 Kandidaten nur in 3 Zellen einer Region erscheinen. Weil diese 3 Zellen zusammen die 3 Kandidaten konsumieren werden, können alle übrigen Kandidaten in diesen 3 Zellen entfernt werden.

Beispiel:
Im linken unteren Block (gelb) erscheinen die Kandidaten 3, 7 und 9 nur in den 3 Zellen R8C1, R9C1 und R9C2 (grün). Also können die übrigen Kandidaten 1, 2, 8 aus den grünen Zellen entfernt werden. Wie Sie sehen, ist es ziemlich schwierig, einen versteckten Dreier aufzuspüren.

Versteckte Tupel

Versteckte Paare und Versteckte Dreier sind ein Spezialfall der allgemeinen Regel Versteckte Tupel. Wenn N Kandidaten nur in N Zellen einer Region erscheinen, dann werden diese N Zellen die N Kandidaten konsumieren. Alle anderen Kandidaten können von den N Zellen entfernt werden.

X-Flügel (X-Wing)

Ich werde diese Regel direkt am Beispiel links erklären. Der Kandidat 9 erscheint in der Reihe R1 (gelb) nur in den 2 Zellen R1C2 und R1C8 (grün). In der Reihe R8 (gelb), erscheint der gleiche Kandidat 9 auch nur in 2 Zellen R8C2 und R8C8 (grün). Die 4 grünen Zellen bilden Ecken eines Rechtecks - sie liegen in 2 Kolonnen. In der Reihe R1 wird entweder die Zelle R1C2 oder die Zelle R1C8 den Wert 9 haben. In der Reihe R8 wird entweder die Zelle R8C2 oder die Zelle R8C8 den Wert 9 haben.

Fall 1: Wenn R1C2 9 erhält, dann kann R8C2 nicht 9 sein und darum muss R8C8 9 sein.
Fall 2: Wenn R1C2 nicht 9 wird, dann muss R1C8 9 werden. Somit wird R8C8 nicht 9 und R1C8 muss 9 werden.

In jedem Fall bekommen genau 2 diagonale Ecken des Rechtecks den Wert 9 ("X-Wing") und darum kann der Kandidat 9 von den Kolonnen C2 und C8 eliminiert werden (ausser aus den Ecken des Rechtecks). 9 wird also aus den roten Zellen entfernt.

Die X-Wing Regel kann sinngemäss auf die Situation angewendet werden, wo die Rollen von Reihen und Kolonnen vertauscht werden.

Andere Logische Regeln

Es gibt viele anderen logischen Regeln für die Lösung von Sudoku mit phantasievollen Namen wie: Sie finden sie im Internet.

Rohe Gewalt und Backtracking

Wenn Sie keine logische Regel anwenden können, so können Sie die Methode des Versuch-und-Irrtums probieren. Dies sollte nicht zu oft geschehen - es gibt nämlich zu viele Möglichkeiten: 6670903752021072936960.

Sie können die Methode trotzdem versuchen, wenn eine Zelle nur 2 (höchstens 3) Kandidaten enthält. Sie würden sich diese Zelle merken und den ersten Kandidaten probieren. Wenn Sie Glück haben, kommen Sie zu einer Lösung. Wenn Sie auf eine widersprüchliche Situation stossen, kehren Sie zu der gemerkten Zelle zurück (mit Hilfe der Befehle Zurück) und probieren den zweiten Kandidaten. Es kann leider passieren, dass Sie während eines Versuchs wieder auf eine Zelle mit mehreren Möglichkeiten stossen. Sie müssen sich dann auch diese Zelle merken und das Spiel wiederholen. Diese Methode des systematischen Ausprobierens aller Möglichkeiten durch Vor- und Zurückgehen heisst Backtracking. Sie entspricht der Suche in einem Labyrinth mit Hilfe des Ariadnefadens.