Zahlwort

Jetzt habe ich einige Sudoku hinter mir, die Rate der Leicht­sinns­fehler ist gesunken, und ich kann nunmehr auch als mittel­mäßig bezeich­nete Aufgaben ohne Zusatz­notizen in zwanzig Minuten lösen. Den Lösungs­weg eines nicht zu schweren Sudoku mit 28 vor­gege­benen Ziffern habe ich aufge­zeichnet, um mit der Vor­gehens­weise eines Compu­ters zu verglei­chen. Erstaun­licher­weise ging das Programm [2] völlig anders vor als ich und begann sofort mit ganz einfachen Kombi­nati­onen, die ich überhaupt nicht sah. Doch waren unsere Fort­schritte letzt­lich gar nicht sehr ver­schieden, weil von beiden der gleiche Engpaß zu über­winden war, wie das bei einem ordent­lichen Sudoku zu sein hat, auch wenn es leicht ist:

┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓
┃   │ 8 │   ┃   │   │   ┃   │ 2 │   ┃
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
┃ 2 │   │   ┃   │ 8 │   ┃   │   │ 9 ┃
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
┃   │   │ 1 ┃   │ 4 │   ┃ 3 │   │   ┃
┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫
┃ 3 │ 5 │   ┃   │   │   ┃   │   │ 4 ┃
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
┃   │   │ 2 ┃ 1 │ 3 │ 9 ┃   │   │ 8 ┃
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
┃   │   │ 9 ┃ 6 │   │   ┃   │ 3 │   ┃
┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫
┃ 1 │   │   ┃ 2 │   │   ┃   │   │   ┃
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
┃   │ 2 │   ┃   │   │ 7 ┃   │ 1 │   ┃
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
┃   │   │   ┃ 8 │   │ 5 ┃ 7 │ 4 │   ┃
┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛

[Dieses Sudoku als HTML-​Tabelle wurde schlecht ange­zeigt, später verschwanden hier alle Tabellen mit der Nach­editie­rung eines Bei­trages. Deshalb habe ich mir die Mühe gemacht, das vorste­hende Sudoku-​Diagramm allein mit Unicode-​Zeichen darzu­stellen. Doch leider gibt es auch nach Jahr­zehnten moderne Geräte wie Mobil­telefone, die im Gegen­satz zu meinem veral­teten Firefox immer noch nicht in der Lage sind, Unicode-​Rahmen vor­schrifts­mäßig anzu­zeigen. Den HTML-​Text kann sich jeder hier raus­kopieren, doch gibt es auch ein Bild, das ersatz­weise einzu­fügen mir wegen des Schärfe­ver­lustes wider­strebt, auch wenn er in diesem Falle noch erträg­lich wäre und der moderene Mensch dank seiner Winz-​Bildern damit zufrieden ist. Und da ich gerade dabei bin: Es geht mir auch auf die Eier, daß hier in meinem Blog orange als Farbcode herausgefiltert wird und ich es durch #ff8800 ersetzen mußte.]

Zur Lösung des vorste­henden Sudoku [1] genügt eine einfache Grund­idee: Für jedes Gebiet (Zeile, Spalte, Block) wird ein quadra­tisches Diagramm ‚gezeich­net‘, das zu allen offenen Feldern angibt, welche der fehlen­den Ziffern noch ohne direk­ten Wider­spruch ein­trag­bar sind. Für den mitt­leren 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 |

Links ist noch einmal der Mittel­block zu sehen, dessen freie Felder mit A bis E bezeich­net sind und an dem links, rechts, oben und unten steht, welche Ziffern in welchen Zeilen und Spalten aus­scheiden. Aus den fünf freien Feldern A bis E und den noch feh­lenden Zif­fern 2, 4, 5, 7 und 8 ist im mitt­leren Bild eine Matrix gebildet, in der mit o vermerkt ist, welche Ziffern in welchen Feldern noch möglich sind. Blau hervor­gehoben ist die ein­zige Möglich­keit, fünf dieser o derart auszu­wählen, daß in jeder Zeile und jeder Spalte genau eines fällt.

Damit ist der Mittelblock voll­ständig gelöst. Im allge­meinen aber klappt das nicht so gut, und es lohnt sich auch nicht, für alle 27 Gebiete ein solches Bild zu malen. Vielmehr ist es zumeist völlig aus­reichend, Felder zu finden, in die nur noch eine Ziffer paßt (rot, nackter Einer) und in Zeilen, Spalten und Blöcken zu schauen, ob für eine Ziffer nur noch ein Feld bleibt (grün, versteckter Einer).

Der Computer und meine kleine Tochter bevor­zugen die rote Methode, mit der man jedes belie­bige freie Feld testen kann: Sind in den drei Gebieten (Zeile, Spalte, Block) dieses Feldes acht verschie­dene Ziffern, so ist die neunte die gesuchte. So ein­fach diese Methode auch ist, hat sie doch zwei Nach­teile: In einem schweren Sudoku kommt man damit zumin­dest am Anfang nicht weit. Und von ein­fachen Fällen abge­sehen sieht der Mensch nur schlecht, an welcher Stelle diese Methode Erfolg ver­spricht.

Ich bevorzuge deshalb die grüne Methode, obwohl sie voll­stän­dig ange­wendet den drei­fachen Über­prüfungs­aufwand erfor­dert. Es ist deshalb wichtig, nur die erfolg­verspre­chenden Objekte zu über­prüfen. Das sind die mit wenigen freien Feldern. Und zu Beginn betrachte ich für jede Ziffer alle Blöcke gleich­zeitig, indem ich mir waage­rechte und senk­rechte Balken durch die Ziffern denke und schaue, in welchem Block sie nur noch in einem ein­zigen Käst­chen möglich sind.

Im folgenden Vergleich meiner Lösung mit der eines Computer-​Pro­gram­mes [2] entspre­chen die Farben der Ziffern dieser roten bzw. grünen Methode, wobei ich aller­dings blau benutze, wenn die grüne Methode nicht auf Blöcke, sondern auf Zeilen oder Spalten ange­wendet wird.

             meine Lösung                            Computerlösung

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

Ich bin die Ziffern von 1 bis 9 einmal   Ich benutze die rote Methode nur in
nach der grünen Methode durchgegangen,   einfachen Fällen und zu Beginn gar
habe also darauf verzichtet, in einem    nicht, weil in schweren Rätseln kaum
zweiten Durchgang noch weitere Treffer   etwas herauskommt und in einfachen zu
zu finden. Es hätte auch ausgereicht,    viel Zeit für die Suche draufgeht. Für
in jedem der sechs 3x9-Streifen nach     einen Computer liegen die Verhältnisse
doppelten Ziffern mit möglichen Kon-     anders. Hier hat er Glück und findet
sequenzen zu suchen, obwohl dann die     die einzige rote Möglichkeit, nämlich
grünen Vieren nicht entdeckt worden      die rote 7 im mittleren Block. Nach
wären. Aber ich versuche, das ganze      diesem Anfang käme auch ein Mensch
Sudoku zu überblicken, was letztlich     zügig voran. Der Computer findet nach
schneller ist als das Durchhecheln von   der roten 7 die rote 2, sodann 8 und 5
3x9-Streifen. Zum Dank blieben sofort    gefolgt von 4 und 6. Weiter mit der nun
zwei Einzelfelder übrig, die nach der    orange dargestellten roten Methode geht
roten Methode mit Siebenern besetzt      es mit 9 und 3 gefolgt von 1, 2 und 7.
werden konnten. Danach folgt auf die     Schließlich stellen die fetten Ziffern
gleiche Weise die rote 6. Damit ist der  8 und 1 den 3x9-Streifen bis auf vier
mittlere waagerechte 3x9-Streifen bis    Felder fertig. Damit ist ein mit meiner
auf zwei Feldpaare ausgefüllt. Um diese  Methode vergleichbares Ergebnis erzielt.
kümmert man sich besser nicht, weil die  Es fehlen einige Zahlen im Umfeld, doch
darin möglichen Ziffern 4 und 7 bzw.     ist die strategisch wichtige orange 3
5 und 6 weitgehend vertauschbar sind.    unten links gefunden.

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

Weil es so schön war, wiederhole ich     Nun ist die rote Methode zunächst am
die grüne Methode. Erwartungsgemäß er-   Ende. Der Computer zieht meines Erach-
bringt sie kaum sofort sichtbaren Fort-  tens  die blaue der grünen Methode vor
schritt. Auch die rote 6 nicht. Deshalb  und findet einige Ziffern, die ich im
greife ich zu der blauen Methode. Für    zweiten Durchgang ebenfalls erhielt.
Zeilen und Spalten mit zwei freien Fel-  Nur die Lage bei den Dreiern ist etwas
dern bringt sie nichts. Bei denen mit    anders. Als konsequenter Anwender der
drei Leerstellen eigentlich auch nicht,  roten Methode erhält der Computer nun
doch beachte ich nebenbei rote Konse-    aber die roten Ziffern 5, 9, 3 und 6,
quenzen: In der letzten Zeile fehlen     gefolgt von der orangen 3. Der Unter-
Ziffern 3, 6 und 9, die zwar alle drei   schied zu meinem Diagramm ist weder
in mehreren Positionen möglich sind,     groß noch von Bedeutung.
doch stehen 6 und 9 beide bereits in
der dritten Spalte, womit die rote
Methode die rote 3 liefert.

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

Die 3 im Block unten links erweist sich  Wieder hat die rote Methode nichts mehr
als Durchbruch. Zunächst liefert die     ergeben, weshalb der Computer erneut
grüne Methode die oberen Dreien, danach  zur blauen greift. Dank seiner Konse-
die 5 und die 9 der vierten Spalte, im   quenz, auch Felder zu überprüfen, die
Anschluß die 4 und die 6 in der zweiten  dem Menschen wenig erfolgversprechend
Zeile, gefolgt von 9, 5 und 4 in der     erscheinen, findet er einige nützliche
ersten Zeile. Unmittelbare Konsequenz    Belegungen mehr als ich, aber 4 und 6
sind die beiden roten Ziffern 5 und 6.   in der zweiten Zeile erst später.

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

Der Rest ist einfach. Die blaue Methode  Auch der Computer kommt an die Stelle,
wird auf die letzte Zeile sowie auf die  wo die widerspenstigen Sechsen auf einen
Spalten 3, 5 und 8 angewendet. Danach    Schlag fallen. Der Rest ist gnadenlose
sind nur noch die Löcher aufzufüllen.    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 |                | 9 8 5 | 3 7 6 | 4 2 1 |
      | 2 3 4 | 5 8 1 | 6 7 9 |                | 2 3 4 | 5 8 1 | 6 7 9 |
      | 7 6 1 | 9 4 2 | 3 8 5 |                | 7 6 1 | 9 4 2 | 3 8 5 |
      +-------+-------+-------+                +-------+-------+-------+
      | 3 5 6 | 7 2 8 | 1 9 4 |                | 3 5 6 | 7 2 8 | 1 9 4 |
      | 4 7 2 | 1 3 9 | 5 6 8 |                | 4 7 2 | 1 3 9 | 5 6 8 |
      | 8 1 9 | 6 5 4 | 2 3 7 |                | 8 1 9 | 6 5 4 | 2 3 7 |
      +-------+-------+-------+                +-------+-------+-------+
      | 1 4 7 | 2 9 3 | 8 5 6 |                | 1 4 7 | 2 9 3 | 8 5 6 |
      | 5 2 8 | 4 6 7 | 9 1 3 |                | 5 2 8 | 4 6 7 | 9 1 3 |
      | 6 9 3 | 8 1 5 | 7 4 2 |                | 6 9 3 | 8 1 5 | 7 4 2 |
      +-------+-------+-------+                +-------+-------+-------+

Dem aufmerksamen Leser wird nicht entgangen sein, daß ich immer von der roten Methode sprach, wenn in einem ein­zigen Gebiet bereits acht Ziffern standen, obgleich die grüne Methode das gleiche Ergeb­nis gelie­fert hätte. Es handelt sich also um einen Einer, der zugleich nackt und ver­deckt ist. Rot habe ich ihn genannt, weil er zumeist dadurch ent­deckt wird, daß man schaut, welche Ziffer noch fehlt, sie einfach ein­trägt und nicht dumm fragt, in welchem freien Feld sie denn stehen könnte.

Ich bin etwas enttäuscht zu sehen, wie ein Computer fast alle Sudoku aus Zeitungen und vielen Heften allein mit nackten und ver­steckten Einern lösen kann. Eigent­lich muß man nur ein guter Buch­halter sein, sich in allen leeren Feldern die Rest­möglich­keiten ein­tragen, um sodann nach Feldern mit nur noch einer Ziffer und manchmal nach einer Ziffer mit nur noch einem Feld zu suchen.

[1] .8.....2.2...8...9..1.4.3..35......4..2139..8..96...3.1..2......2...7.1....8.574.

[2] Andrew Stuart: Sudoku Solver. Nach fast 20 Jahren weicht er auf [1] angesetzt leicht von meiner Computer­lösung ab, obwohl ich nicht sehe, daß an der Reihenfolge der stets abzu­klap­pernden Metho­den sich etwas geän­dert hat. Mög­licher­weise hatte ich ein anderes Pro­gramm ver­wendet.

Anfang  | Paare  | Raster | Stufen