Methoden 1+2 (Quelle: Wikipedia)

🔢 Sudokus interaktiv lösen mit Computer-Unterstützung

Definitionen: Die Einheit ist der Oberbegriff für Zeile, Spalte und Subquadrat ('Block') und besteht damit immer aus 9 Feldern, in denen jede Ziffer von 1...9 genau einmal vorkommen muß.
Mit Kandidaten für ein Feld bezeichnet man die Ziffern, die in der zugehörigen Zeile & Spalte & Quadrat noch nicht eingetragen sind (gibt es für ein Feld nur noch einen Kandidaten, greift Methode 1, s.u.).

Schwierigkeitskategorien

Ein Sudoku ist leicht, wenn Methode 1 zum Lösen ausreicht. Braucht man zusätzlich Methode 2, ist es in der mittleren Kategorie. Sind außerdem noch Methoden 3 und/oder 4 nötig, bezeichnet man es als schwer. Reichen alle 4 Methoden nicht aus, ist es sehr schwer. Die Methoden 1 & 2 sind am einfachsten zu verstehen, 3 & 4 sind komplexer. Die Methoden aber sind nicht unabhängig voneinander: 1 & 3 lassen sich durch 2 & 4 ersetzen.

Methode 1: Auschlußverfahren für Felder (Durchzählen in Einheiten)

Suche nach leeren Feldern, auf denen 8 Ziffern ausgeschlossen sind, weil sie in der gleichen Spalte, Zeile bzw. Subquadrat auftauchen.
Beispiel rechts: auf dem blauen Feld in der Mitte muß die '5' stehen, weil alle anderen 8 Ziffern durch die blau umrandeten Felder ausgeschlossen sind.

Methode 2: Ausschlußverfahren für Ziffern (Sichten von Ziffern)

Prinzip: Jede Ziffer muß in jeder Einheit mindesten einmal vorkommen. Die Methode ist recht aufwendig, denn um sie systematisch anzuwenden, muß man alle noch nicht vorhandenen Ziffern in allen 27 Einheiten (9 Zeilen + 9 Spalten + 9 Quadrate) testen.
Beispiel rechts: Im grünen Feld   muß die '5' stehen, weil die anderen 8 Felder im Subquadrat rechts, oben für die 5 durch die mit roten Linien markierten Zeilen/Spalten verboten sind. Als Such-Einheit dient hier also das oberste rechte Subquadrat.
749156 8 
      4 9
       7 
        5
        6

Methode 3: Twin-Methode (Doppelzwilling)

Prinzip: Wenn in einer Einheit (Zeile/Spalte/Quadrat) bereits 7 Felder gefüllt sind, haben die beiden übrigen Felder die zwei gleichen Kandidaten. D.h. in jedem dieser Felder muß eine dieser beiden Ziffern stehen.
Das kann man u.U. ausnutzen, wie im Beispiel rechts: Die zwei Felder   in der ersten Zeile haben das gleiche Kandidatenpaar (2,3). Die beiden Zahlen 2 und 3 sind damit auf allen anderen Feldern im letzten Quadrat ausgeschlossen, auch in Feld  . Da dieses nur die Kandidaten (1,2,3) hat, kann man folglich hier 1 eintragen.
Das Verfahren funktioniert genauso für Drillinge in einer Einheit (s.u.).
Um die Methode anwenden zu können, muß es Einheiten geben, in denen bereits mind. 6 Felder gefüllt sind.
    1 
1953 8
    6 
   28 
   635
   17 

Methode 4: Globale Paarsuche

Diese Methode erfordert viel Erfahrung und Zeit, da sie u.U. mehrfach (rekursiv) angewandt werden muß, um ein Feld zu lösen.
Vorgehensweise: Man sucht global nach Einheiten (Zeile/Spalte/Quadrat) mit Kandidatenpaaren auf zwei Feldern (Erweiterung von Methode 3).
Beispiel rechts (entnommen aus Example 15, einfache Anwendung führt zum Ziel): Die zwei Felder   in der letzen Spalte haben das gleiche Kandidatenpaar (2,4).
Die beiden Felder   haben jeweils die Kandidatenquadrupel (2,4,7,9) Davon sind nun 2 und 4 ausgeschlossen (gleiche Spalte wie das Paar), und es kommen nur noch die Zahlen (2,7) in Frage, die damit wieder ein Kandidatenpaar bilden. Folglich sind (2,7) auf den restlichen 7 Feldern des Quadrats oben, rechts ausgeschlossen.
Das Feld   hat nur die Kandidaten (2,4), wobei nach Obigem die 2 augeschlossen ist. Folglich kann man hier 4 eintragen.
Im wesentlich komplizierteren Beispiel 17 (noch 40 Felder frei) braucht man aber drei Stufen zur Lösung:
  1. Ausgangspunkt ist in Zeile 3 das Paar (6,7) -> Ausschluß der 7 auf allen anderen Feldern in dieser Zeile.
  2. Das erzeugt in Spalte 5 ein neues Paar (3,8) -> Ausschluß der 8 in dieser Spalte.
  3. Neues Paar (2,7) im Subquadrat 8 -> Feld in Zeile 9 + Spalte 5 (mit den vorherigen Kandidaten 6,7) = 6.

Methode 5: Drillinge

Im Beispiel rechts bilden die drei Felder     in der letzten Zeile einen Drilling, dh sie haben gemeinsam die drei Kanditaten (7,8,9) (nach Subquadratregel).
Das heißt, jede dieser drei Zahlen taucht in genau einem dieser drei Felder auf, auch wenn die konkrete Belegung noch unbekannt ist.
In allen anderen Felder dieser Zeile kann man diese drei Zahlen folglich ausschließen. Da das Feld   in dieser Zeile nur die vier Kandidaten (6,7,8,9) hat, kann man hier 6 eintragen.
Die Regel ist immer dann anwendbar, wenn die drei leeren Felder eine Vereinigungsmenge mit drei Ziffern haben.
Das Prinzip läßt sich für alle 27 Einheiten (9 Zeilen + 9 Spalten + 9 Subq) anwenden, die einen Drilling haben.
(numerisch ist das recht aufwendig, da jede Einheit 9*8*7/6 = 84 potentielle Drillings-Kombinationen hat)
1
2
3
123
456
45

Methode 6: Kandidaten-Reduktion

(neu 7/2020: nicht auf der Wikipedia-Seite erwähnt)
Prinzip: Eigentlich recht simpel: Die Kandidaten für ein Feld lassen sich u.U. reduzieren, wenn man Zusatzinformationen aus anderen Einheiten benutzt.
Im Beispiel rechts hat das Feld   links unten die Kandidaten (3,8).
Da im Feld   die 8 ausgeschlossen ist (Spaltenregel), muß sie in einem der Quadrate    stehen (Subquadratregel).
Folglich kann man hier 3 eintragen.
Diese Methode läßt sich mit allen anderen Methoden kombinieren.
Allgemein muß man die Überlappungsfelder von Subquadraten mit Zeilen/Spalten untersuchen.
1
5
7 8
24 93
9 412
6

Beispiel-Sudokus lösen

Alle Beispiele hier sind eindeutig lösbar (außer das letzte, als Beispiel für ein fehlerhaftes Sudoku: Es hat zwei Lösungen). Für die sehr schweren Sudokus (Beispiele 1-5) reichen die obigen 4 Methoden jedoch nicht aus, um sie komplett zu lösen.
Der Computer kann sie trotzdem mit 'brute force'-Methode ('backtrace') lösen (Button unten).
Beim interaktiven Lösen mit Computer werden je nach Lösungs-Methode die benutzen Einheiten/Felder/Paare farblich hervorgehoben. Wenn die Checkbox Kandidaten aktiviert ist, werden als Hilfestellung die Kandidaten der leeren Felder angezeigt. Bewegt man dann die Maus über dem Sudoku, sind dies die Kanditaten vor dem Eintragen der zuletzt gelösten Zahl (zur Illustration des Lösungswegs).
Um ein neues Sudoku mit Computer-Unterstützung zu lösen, löscht man zuerst das aktuelle (mit Button oder Auswahl von Example 0). Dann kann man die Ziffern der Vorlage mit der Tastatur in das Sudoku einfügen. Danach gibt man genauso die eigenen Versuche ein (oder läßt es den Computer lösen 🙂). Wenn dabei die Checkbox check unten aktiviert ist, werden sie vom Computer auf Richtigkeit getestet (dazu muß aber die Vorlage bereits vollständig eingegeben sein!).
Den aktuellen Stand kann man jederzeit ausdrucken ('print'-Button) oder lokal speichern ('store'-Button). Aber Achtung: Lokal gespeicherte Sudokus gehen beim Löschen des Browser-Caches verloren!
Beispiel...


Kandidaten autofill check
Methoden 1 2 3 4 5 6
Tabelle aller Examples
Anklicken einer Tabellenzeile lädt das Beispiel in das Sudoku links. Horizontale Bewegung des Mauszeigers über die Spalte 'Lösungs-Sequence' füllt es interaktiv.
Der Computer simuliert hier die menschliche Lösungsweise: Zuerst wird immer Methode 1 probiert. Führt sie nicht weiter, kommt Methode 2 dran, usw. bis Methode 6. Dann wird wieder mit 1 begonnen, usw. bis das Sudoku entweder komplett gelöst ist, oder keine Methode mehr funktioniert.
Die Farben der Ziffern im Sudoku codieren die benutzte Methode (0 = Vorgabe, 7 = Benutzer-Eingabe):
In der Spalte Lösungs-Sequence werden die vom Computer benutzte Methoden für die Lösung angezeigt
  1. Die Ziffern 1...9 in der Sequence sind mit Methode 1 gelöst
  2. Die Zeichen 'zsq' sind Methode 2 (angewandt für Zeilen, Spalten bzw. Quadrate)
  3. '*' ist Methode 3
  4. '+' ist Methode 4
  5. 'D' ist Methode 5
  6. 'X' ist Methode 6
Mit den Checkboxen 'Methoden' (linke Seite ) kann man einzelne Methoden für den Computer ein-/ausschalten
Der Button 'Neues Sudoku' erzeugt ein zufälliges Sudoku mit einstellbarem maximalen Schwierigkeitsgrad (rmax = 1...6). Dieses kann man hier im Browser lösen oder mit dem print-Button ausdrucken (auch mehrere auf einer A4-Seite).

Die Anzahl der Sudokus

Es gibt genau 6.670.903.752.021.072.936.960 ≈ 6,7 ⋅ 1021 verschiedene (fertig ausgefüllte) Sudokus (Wikipedia). Davon sind aber nur 5.472.730.538 wesentlich voneinander verschieden.
Die restlichen gehen aus diesen ≈ 5,4 ⋅ 109 Sudokus durch folgende Symmetrie-Operationen hervor: Damit lassen sich aus jedem Sudoku 362,880 × 1296 × 1296 × 2 ≈ 1,218998 ⋅ 1012 neue Sudokus erzeugen, die (außer in wenigen Ausnahmefällen?) alle voneinander verschieden sind.
Die Anzahl der Sudoku-Aufgaben (mit gelöschten Ziffern) ist natürlich um viele Zehnerpotenzen größer.

Normalisierung eines (gefüllten) Sudokus

Vorgehensweise: man permutiert die Ziffern so, daß im 1. Subquadrat die Zeilen 123,456,789 stehen. Die Spalten 4-9 ordnet man so um, daß in der 1. Zeile in Spalte 4 die '4' steht.
Die Spalten 5-9 kann man dann so umordnen, daß genau 10 Möglichkeiten bleiben (die Ziffern (a,b) in den Spalten (5,6) und (7,8,9) aufsteigend): 56,789 57,689 58,678 59,678 67,589 68,579 69,578 78,569 79,568 89,567.
Analog geht man mit Spalte 1 vor: die Zeilen 6-9 werden so umgeordnet, daß in Zeile 4 die 2 steht. Dann gibt es wieder 10 Möglichkeiten für die Verteilung der Ziffern 3,5,6,8,9 auf die Zeilen 5-9.
1234ab
456
789
2
x
y
.....

Letzte Änderung:      wolfk.wk@wolfk-wk.de