Zahlwort

Jetzt habe ich einige Sudoku hinter mir, die Rate der Leichtsinnsfehler ist gesunken, und ich kann nunmehr auch als mittelmäßig bezeichnete Aufgaben ohne Zusatznotizen in zwanzig Minuten lösen. Den Lösungsweg eines nicht zu schweren Sudoku mit 28 vorgegebenen Ziffern habe ich aufgezeichnet, um mit der Vorgehensweise eines Computers zu vergleichen. Erstaunlicherweise ging das Programm völlig anders vor als ich und begann sofort mit ganz einfachen Kombinationen, die ich überhaupt nicht sah. Doch waren unsere Fortschritte gar nicht sehr verschieden, weil von beiden der gleiche Engpaß zu überwinden war, wie das bei einem ordentlichen Sudoku zu sein hat, auch wenn es leicht ist:

­ 8 ­ 2 ­ ­ ­ ­ 1	­ ­ ­ ­ 8 ­ ­ 4 ­	­ 2 ­ ­ ­ 9 3 ­ ­
3 5 ­ ­ ­ 2 ­ ­ 9	­ ­ ­ 1 3 9 6 ­ ­	­ ­ 4 ­ ­ 8 ­ 3 ­
1 ­ ­ ­ 2 ­ ­ ­ ­	2 ­ ­ ­ ­ 7 8 ­ 5	­ ­ ­ ­ 1 ­ 7 4 ­

[Es ist ärgerlich, wie schlecht hier vor allem Tabellen umgesetzt werden. Das ist wohl der Preis dafür, daß der Kalender am rechten Rand ordentlich aussieht und für Absätze nur die Zeile zu wechseln ist. Ich ändere jetzt aber nichts an den Voreinstellungen und lebe mit den zu großem Abständen hier und dem zentrierten Text weiter unten.]

Erstaunlicherweise genügt sowohl dem Computer als auch mir die einfachste aller Grundideen: Für jedes Gebiet (Zeile, Spalte, Block) wird ein quadratisches Diagramm gezeichnet, daß zu allen offenen Feldern angibt, welche der fehlenden Zahlen noch ohne direkten Widerspruch eintragbar ist. Für den mittleren Block sieht das wie folgt aus:

    | . 8 . |
    | . 4 . |         | 2 4 5 7 8     |       |
----+-------+----   --+----------   --+-------+--
3 5 | A B C | 4 .   A | . . . o .     | 7 2 8 |
. 2 | 1 3 9 | 8 .   B | o . . o .     | 1 3 9 |
. 9 | 6 D E | 3 .   C | o . . . o     | 6 5 4 |
----+-------+----   D | o . o o .   --+-------+--
    | 2 . 7 |       E | o o . . o     |       |
    | 8 . 5 |

Blau markiert ist die einzige Möglichkeit, in jeder Zeile und in jeder Spalte genau eine gültige Kombination o zu haben, womit der Mittelblock vollständig gelöst ist. Im allgemeinen aber klappt das nicht so gut, und es lohnt sich auch nicht, für alle 27 Gebiete ein solches Bild zu malen. Doch ist es zumeist völlig ausreichend, mit der einen Methode die rot markierten Felder zu finden, in die nur noch eine Ziffer paßt, und mit der anderen Methode die grün markierten Ziffern, für die nur noch ein Feld bleibt.

Der Computer und meine kleine Tochter bevorzugen die rote Methode, mit der man jedes beliebige freie Feld testen kann: Sind in den drei Gebieten (Zeile, Spalte, Block) dieses Feldes acht verschiedene Ziffern, so ist die neunte die gesuchte. So einfach diese Methode auch ist, hat sie doch zwei Nachteile: In einem schweren Sudoku kommt man damit zumindest am Anfang nicht weit. Und von einfachen Fällen abgesehen sieht der Mensch nur schlecht, an welcher Stelle diese Methode Erfolg verspricht.

Ich bevorzuge deshalb die grüne Methode, obwohl sie vollständig angewendet den dreifachen Überprüfungsaufwand erfordert. Es ist deshalb wichtig, nur die erfolgversprechenden Objekte zu überprüfen. Das sind die mit wenig freien Feldern. Zu Beginn überprüfe ich für jede Ziffer alle Blöcke gleichzeitig, indem ich mir waagerechte und senkrechte Balken durch die Ziffer denke und schaue, in welchem Block nur noch ein Feld frei bleibt.

Im folgenden Vergleich meiner Lösung mit der des Computers entsprechen die Farben der Ziffern dieser roten bzw. grünen Methode, wobei ich allerdings blau benutze, wenn die grüne Methode nicht auf Blöcke, sondern auf Zeilen oder Spalten angewendet wird.

meine Lösung	­	Computerlösung
+-------+-------+-------+ | . 8 . | . . . | . 2 1 | | 2 . . | . 8 1 | . . 9 | | . . 1 | . 4 2 | 3 8 . | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | . . 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 . . | 2 . . | . . . | | . 2 . | 4 . 7 | . 1 . | | . . . | 8 1 5 | 7 4 2 | +-------+-------+-------+	­	+-------+-------+-------+ | . 8 . | . . . | . 2 . | | 2 . . | . 8 . | . . 9 | | . . 1 | . 4 . | 3 . . | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | . . 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 . . | 2 . . | . . . | | . 2 . | . . 7 | . 1 . | | . . 3 | 8 . 5 | 7 4 . | +-------+-------+-------+
Ich bin die Ziffern von 1 bis 9 einmal nach der grünen Methode durchgegangen, habe also darauf verzichtet, in einem zweiten Durchgang noch weitere Treffer zu finden. Es hätte auch ausgereicht, in jedem der sechs 3x9-Streifen nach doppelten Ziffern mit möglichen Konsequenzen zu suchen, obwohl dann die grünen Vieren unentdeckt geblieben wären. Aber ich versuche, das ganze Sudoku zu überblicken, was letztlich schneller ist als das Durchhecheln von 3x9-Streifen. Zum Dank blieben sofort zwei Einzelfelder übrig, die nach der roten Methode mit Siebenern zu besetzen waren. Danach folgt auf die gleiche Weise die rote 6. Als Ergebnis ist der mittlere waagerechte 3x9-Streifen bis auf zwei Feldpaare ausgefüllt. Um die kümmert man sich besser nicht, weil die darin möglichen Ziffern 4 und 7 bzw. 5 und 6 weitgehend vertauschbar sind.	­	Ich benutze die rote Methode nur in einfachen Fällen und zu Beginn gar nicht, weil in schweren Rätseln nichts herauskommt und für einfache zu viel Zeit für die Suche draufgeht. Für einen Computer liegen die Verhältnisse anders. Hier hat er Glück und findet die einzige rote Konsequenz, nämlich die rote 7 im mittleren Block. Nach diesem Anfang käme auch ein Mensch zügig voran. Der Computer findet nach der roten 7 die rote 2, sodann 8 und 5 gefolgt von 4 und 6. Weiter mit der roten Methode, jedoch orange dargestellt, geht es mit 9 und 3 gefolgt von 1, 2 und 7. Schließlich stellen die fett dargestellten Ziffern 8 und 1 den 3x9-Streifen bis auf vier Felder fertig. Es ist fast das gleiche Ergebnis erzielt, wie ich es mit meiner Methode erhielt. Es fehlen zwar einige Zahlen im Umfeld, dafür ist die strategisch wichtige orange 3 unten links gefunden, gleichwohl sie unmittelbar nichts nützt. Wegen ihrer abseitigen Lage, hätte ich sie bei Anwendung der roten Methode übersehen.
+-------+-------+-------+ | . 8 . | . 7 6 | . 2 1 | | 2 . . | . 8 1 | . 7 9 | | . . 1 | . 4 2 | 3 8 . | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | . . 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 . . | 2 . 3 | . . . | | . 2 . | 4 . 7 | . 1 3 | | . . 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+	­	+-------+-------+-------+ | . 8 . | 3 7 6 | . 2 1 | | 2 3 . | 5 8 1 | . . 9 | | . . 1 | 9 4 2 | 3 8 . | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | . . 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 . . | 2 . 3 | . . . | | . 2 . | 4 . 7 | . 1 3 | | . . 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+
Weil es so schön war, wiederhole ich die grüne Methode. Erwartungsgemäß erbringt sie kaum sofort sichtbaren Fortschritt. Auch die rote 6 nicht. So greife ich zur blauen Methode. Für Zeilen und Spalten mit zwei freien Feldern bringt sie nichts. Bei denen mit drei Leerstellen eigentlich auch nicht, doch beachte ich in solchen Fällen nebenbei rote Konsequenzen: In der letzten Zeile fehlen die Ziffern 3, 6 und 9, die zwar alle drei in mehreren Positionen möglich sind, doch stehen 6 und 9 beide bereits in der dritten Spalte, womit die rote Methode die rote 3 liefert.	­	Nun ist die rote Methode zunächst am Ende. Der Computer zieht die blaue der grünen Methode vor und findet eine Reihe von Ziffern, die ich nach meiner Methode im zweiten Durchgang ebenfalls erhielt. Nur die Lage bei den Dreiern ist etwas unterschiedlich. Als konsequenter Anwender der roten Methode erhält der Computer nun aber die roten Ziffern 5, 9, 3 und 6, gefolgt von der orange eingezeichneten 3. Der Unterschied zu meinem Diagramm ist weder groß noch von Bedeutung.
+-------+-------+-------+ | 9 8 5 | 3 7 6 | 4 2 1 | | 2 3 4 | 5 8 1 | 6 7 9 | | . . 1 | 9 4 2 | 3 8 5 | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | . . 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 . . | 2 . 3 | . . 6 | | . 2 . | 4 . 7 | . 1 3 | | . . 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+	­	+-------+-------+-------+ | 9 8 . | 3 7 6 | . 2 1 | | 2 3 . | 5 8 1 | . 7 9 | | . . 1 | 9 4 2 | 3 8 . | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | 4 7 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 4 7 | 2 . 3 | 8 . . | | . 2 8 | 4 . 7 | 9 1 3 | | . 9 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+
Die 3 im Block unten links erweist sich als der Durchbruch. Zunächst liefert die grüne Methode die oberen Dreien, im Anschluß die blaue Methode 5 und 9 in der vierten Spalte, dann 4 und 6 in der zweiten Zeile, gefolgt von 9, 5 und 4 in der ersten Zeile. Unmittelbare Konsequenz sind die beiden roten Ziffern.	­	Wieder hat die rote Methode nichts mehr ergeben, weshalb der Computer erneut zur blauen greift. Durch seine gnadenlose Konsequenz, auch Felder zu überprüfen, die für den Menschen wenig erfolgversprechend aussehen, findet er einige nützliche Belegungen mehr als ich. Warum aber nicht 4 und 6 in der zweiten Zeile?
+-------+-------+-------+ | 9 8 5 | 3 7 6 | 4 2 1 | | 2 3 4 | 5 8 1 | 6 7 9 | | . . 1 | 9 4 2 | 3 8 5 | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | . . 2 | 1 3 9 | . 6 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 . 7 | 2 9 3 | . 5 6 | | . 2 8 | 4 6 7 | . 1 3 | | 6 9 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+	­	+-------+-------+-------+ | 9 8 . | 3 7 6 | . 2 1 | | 2 3 4 | 5 8 1 | . 7 9 | | . 6 1 | 9 4 2 | 3 8 . | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | 4 7 2 | 1 3 9 | . . 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 4 7 | 2 . 3 | 8 . . | | . 2 8 | 4 6 7 | 9 1 3 | | 6 9 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+
Der Rest ist mechanische Arbeit. Die blaue Methode wird auf die letzte Zeile sowie die Spalten 3, 5 und 8 angewendet. Danach ist es einfach: Einmal um Uhrzeigersinn die Löcher auffüllen.	­	Auch der Computer kommt an die Stelle, wo die widerspenstigen Sechsen auf einen Schlag fallen. Der Rest ist gnadenlose Routine nach der roten Methode. Erst die roten, dann die orangen und schließlich die fetten Ziffern.
+-------+-------+-------+ | 9 8 5 | 3 7 6 | 4 2 1 | | 2 3 4 | 5 8 1 | 6 7 9 | | 7 6 1 | 9 4 2 | 3 8 5 | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | 4 7 2 | 1 3 9 | 5 6 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 4 7 | 2 9 3 | 8 5 6 | | 5 2 8 | 4 6 7 | 9 1 3 | | 6 9 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+	­	+-------+-------+-------+ | 9 8 5 | 3 7 6 | 4 2 1 | | 2 3 4 | 5 8 1 | 6 7 9 | | 7 6 1 | 9 4 2 | 3 8 5 | +-------+-------+-------+ | 3 5 6 | 7 2 8 | 1 9 4 | | 4 7 2 | 1 3 9 | 5 6 8 | | 8 1 9 | 6 5 4 | 2 3 7 | +-------+-------+-------+ | 1 4 7 | 2 9 3 | 8 5 6 | | 5 2 8 | 4 6 7 | 9 1 3 | | 6 9 3 | 8 1 5 | 7 4 2 | +-------+-------+-------+

Ich bin etwas enttäuscht zu sehen, wie ein Computer fast alle Sudoku mit der roten und der blauen Methode lösen kann, viele sogar mit der roten allein. Nicht weil ich oftmals Mühe mit ihnen habe, sondern weil ich in Bussen und Bahnen vorwiegend Sudoku mit vielen Vorgaben sehe, die wahrscheinlich alle ohne Probleme lösbar sind. Eigentlich muß man nur ein guter Buchhalter sein, sich in allen leeren Feldern die Restmöglichkeiten eintragen, um sodann nach Feldern mit nur noch einer Ziffer (rote Methode) oder nach einer Ziffer mit nur noch einem Feld (grüne bzw. blaue Methode) zu suchen.

Teil 1: Anfang
Teil 2: Einer
Teil 3: Paare
Teil 4: Raster