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

Vorgestern versagten meine üblichen Sudoku-Methoden als ich in folgende Situation geriet:

+-------+-------+-------+
| 2 . 8 | . 7 . | . 6 . |
| . . . | . . 9 | 3 # . |
| 3 9 7 | . . 6 | 5 1 . |
+-------+-------+-------+
| . . . | 6 . . | 1 8 7 |
| . 2 . | . . . | . 4 . |
| 7 . . | 4 9 . | . 3 . |
+-------+-------+-------+
| . 4 . | . 2 . | . 9 . |
| 9 . . | . 6 . | . 5 3 |
| 1 . . | 9 . 5 | 8 . . |
+-------+-------+-------+

Ich habe in allen neun Blöcken überprüft, welche noch fehlenden Ziffern in welche der noch offenen Felder passen, und nichts gefunden. Ich habe alle Zeilen und Spalten nach Ziffern durchgesehen, die nur an zwei Positionen stehen können, doch brachte auch das mich nicht weiter. Ich bemerkte sogar, daß die Ziffern 1, 3 und 5 des Blockes oben rechts in der ersten Zeile an nur drei Positionen möglich sind. Doch aus den nur noch zwei Plätzen für die Restziffern 4 und 9 der ersten Zeile folgte auch nichts. [Doch wie mein Kommentar zu diesem Kommentar aufzeigt, habe ich dennoch elementare Möglichkeiten übersehen.]

Und so sah ich mich doch gezwungen, eine Fallunterscheidung durchzuführen, nämlich an der mit # bezeichneten Stelle eine 2 bzw. eine 7 auszuprobieren. Das Einsetzen einer 2 schien mehr einfache Konsequenzen nach sich zu ziehen, weshalb eine 7 wahrscheinlich richtig sein sollte, was auch der Fall ist. Das probeweise Einsetzen einer 7 hätte mich also zum Ziel geführt.

Doch wie Mathematiker so sind: Sie wollen nicht nur die Lösung, sondern möchten sie auch abgeleitet und nicht geraten haben. Oder sie stellen sich vor, die Eindeutigkeit der Lösung sei nicht bekannt, und wollen sie nachweisen oder alle Lösungen finden. Dann müssen beide Fälle durchgearbeitet werden, am besten erst die mit den besseren Aussichten auf einen Widerspruch. Auch ich konnte über diesen Schatten nicht springen und habe mit wenig Aufwand die 2 zu einem Widerspruch geführt. So konnte ich die 7 einsetzen und wäre ohne weitere Probleme ans Ziel gekommen, wenn mir nicht ein Flüchtigkeitsfehler unterlaufen wäre.

Es bleibt die Frage, ob die gängigen Methoden wirklich nichts mehr hätten bringen können, ob wirklich eine fortgeschrittene Kombination oder gar eine Fallunterscheidung nötig gewesen ist. Dazu habe ich den Computer befragt, und er lieferte in seiner unnachahmlichen Brutalität das einzige freie Feld, in dem nur noch eine Ziffer möglich ist, die 2 im Block links unten:

+-------+-------+-------+
| 2 . 8 | . 7 . | . 6 . |
| . . . | . . 9 | 3 # . |
| 3 9 7 | . . 6 | 5 1 . |
+-------+-------+-------+
| . . . | 6 . . | 1 8 7 |
| . 2 . | . . . | . 4 . |
| 7 . . | 4 9 . | . 3 . |
+-------+-------+-------+
| . 4 . | . 2 . | . 9 . |
| 9 . 2 | . 6 . | . 5 3 |
| 1 . . | 9 . 5 | 8 . . |
+-------+-------+-------+

Wie konnte ich das übersehen, der ich doch alle Blöcke im Detail durchgesehen habe? Nun, ich habe zwar für alle sechs fehlenden Ziffern kontrolliert, in welche Felder sie noch gehen, doch dabei übersehen, daß außer der 2 alle anderen fünf Ziffern das eine Feld meiden, denn es schwer, sechs Ziffern in sechs möglichen Positionen gemeinsam zu überblicken. Auf eine vollständige Überprüfung aller Einzelfelder auf mögliche Einschränkungen auf eine einzige Ziffer hatte ich verzichtet. So erlag ich der Schikane, daß an der einzigen erfolgreichen Stelle gerade besonders wenige Ziffern zu finden waren. Jede der ausgeschlossenen acht Ziffern kommt nur einmal vor.

Einen Computer läßt das kalt. Nach der roten 2 findet er in zwei weiteren Schritten jeweils eine Ziffer, nimmt sich dann zwei Spalten vor und kommt durch einfache Schlüsse auf eine 7 an der mit # bezeichneten Stelle. Und erschwerend kommt hinzu, daß ein Buchhalter die Lösung ebenfalls gefunden hätte. Dazu stelle ich den linken unteren Block vergrößert dar:

| 2 3 7 |  2 9  |  7 8  |      | 2 3 7 |  2 9  |  7 8  |
+-------+-------+-------+--    +-------+-------+-------+--
|       | +---+ |   2 3 | 2    | \ | / | +---+ | \ |   | 2
|   5 6 | | 4 | |   5 6 |      |--     | | 4 | |--     |
|   8   | +---+ |       | 9    | /   \ | +---+ | / | \ | 9
+-------+-------+-------+--    +-------+-------+-------+--
| +---+ |       |   2   | 3    | +---+ | \ | / | \   / | 3
| | 9 | |       |       | 5    | | 9 | |-- o --|-- o --| 5
| +---+ | 7 8   |       | 6    | +---+ |     \ | / | \ | 6
+-------+-------+-------+--    +-------+-------+-------+--
| +---+ |     3 |   2 3 | 5    | +---+ | \ |   | \     | 5
| | 1 | |     6 |     6 | 8    | | 1 | |-- o   |-- o   | 8
| +---+ | 7     |       | 9    | +---+ |   | \ | / | \ | 9
+-------+-------+-------+--    +-------+-------+-------+--

Oben und rechts sind die Ziffern angefügt, die in der zugehörigen Spalte bzw. Zeile ausscheiden. Für den ganzen Block scheiden natürlich 1, 4 und 9 aus. Im linken Diagramm standen zu Beginn in jedem freien Feld alle neun Ziffern, von denen einige ausradiert wurden, weil sie nicht mehr möglich sind. Das rechte Diagramm vermeidet Radierungen. Dafür werden Durchstreichungen an den Zifferpostionen eingetragen. Das Feld mit der einzigen möglichen Ziffer 2 ist in beiden Fällen leicht zu erkennen.

Gut, mit Geduld, Bleistift und Radiergummi hätte ich es auch geschafft, doch nicht schneller als mit meiner Fallunterscheidung. Das Ziel aber ist, gar keine Notizen zu machen. Damit scheidet nicht nur die Buchhaltermethode aus, die Fallunterscheidung ist auch im Kopf zu bewältigen. Und dann ist es sicherlich von Vorteil, erst den zum Widerspruch führenden Zweig in Gedanken auszuführen.

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

+-------+-------+-------+
| 2 . 8 | . 7 . | . 6 . |
| . . . | . . 9 | 3 . . |
| 3 9 7 | . . 6 | 5 1 . |
+-------+-------+-------+
| . . . | 6 . . | 1 8 7 |
| . 2 . | . . . | . 4 . | [1]
| 7 . . | 4 9 . | . 3 . |
+-------+-------+-------+
| . 4 . | . 2 . | . 9 . |
| 9 . . | . 6 . | . 5 3 |
| 1 . . | 9 . 5 | 8 . . |
+-------+-------+-------+

+-------+-------+-------+
| 2 . 8 | . 7 . | . 6 . |
| . . . | . . 9 | 3 7 . |
| 3 9 7 | . . 6 | 5 1 . |
+-------+-------+-------+
| . . 9 | 6 . . | 1 8 7 |
| . 2 . | . . . | . 4 . | [2]
| 7 . . | 4 9 . | . 3 . |
+-------+-------+-------+
| . 4 . | . 2 . | . 9 1 |
| 9 . 2 | . 6 . | . 5 3 |
| 1 . . | 9 . 5 | 8 . . |
+-------+-------+-------+

[1]  2.8.7..6......93..397..651....6..187.2
.....4.7..49..3..4..2..9.9...6..531..9.58.. 

[2]  2.8.7..6......937.397..651...96..187.2
.....4.7..49..3..4..2..9.9.2.6..531..9.58..