|
Was ist Sudoku?
Sudoku ist ein Knobelspiel.
.. .... |
Gegeben ist ein Quadrat aus 9x9=81 Kästchen, in
denen bestimmte Ziffern schon eingetragen sind. Hier sind es 30 Ziffern,
sonst kann die Anzahl bis auf 17 hinuntergehen.
Die Symmetrie in der Verteilung der Ziffern ist eine schöne
Beigabe und hat Tradition. |
Die Aufgabe besteht darin,
die freien Kästchen so mit Ziffern zu besetzen, dass
>in jeder Zeile,
>in jeder Spalte,
>in jedem 3x3-Teilquadrat ("Block") die Ziffern 1 bis
9 vorkommen.
Die Aufgabe stammt von der
deutschen bzw. englischen Wikipedia-Seite.
Lösung:
.. ... |
Das ist die vorweggenommene Lösung.
Sie ist beim "richtigen" Sudoku wie hier eindeutig.
|
Sudoku ist kein Zahlenspiel,
eher ein Ziffernspiel. Die Zahlen werden als Zeichen verwendet.
Statt der Ziffern könnte man auch die Buchstaben
a b c d e f g h k nehmen.
Man denkt bei diesem Spiel
an das Eulersche "lateinische Quadrat", das im weiteren Sinne zu den magischen
Quadraten zählt. Da werden die Zahlen von 1 bis n so in einem nxn-Quadrat
angeordnet, dass in jeder Zeile und Spalte unterschiedliche Zahlen stehen.
Hier ist ein 5x5-Quadrat.
Mehr über das lateinische Quadrat findet man zum Beispiel
bei Wikipedia (URL unten).
Wer Sudoku mag, mag vielleicht
auch das Symbolrätsel.
Lösen
eines leichten Sudokus top
Zum Lösen eines Sudokus gehört
auch der Spaß einen eigenen Lösungsweg zu finden.
Der hier dargestellte Weg ist ein
Weg von vielen und soll keine Musterlösung sein.
In einem ersten Durchgang verwende ich das Drei-Block-Verfahren
oder Scannen.
Dabei wird nacheinander nach den Positionen der Ziffern
Eins bis Neun gesucht. Normalerweise halte ich die Reihenfolge Eins, Zwei,
Drei,... ein. Ausnahmsweise wird hier die Ziffer Drei vorgezogen, um das
Verfahren zu erläutern.
... ... |
Die Suche nach der (vierten) Drei geht von drei nebeneinander
liegenden Blöcken aus, in denen sich genau zwei Dreien befinden.
In diesen Falle sind es die drei mittleren Blöcke
mit zwei Dreien rechts.
Eine weitere Drei muss in der sechsten Zeile und dem
Block links liegen. Nur zwei Kästchen sind unten frei. In der zweiten
Spalte steht ganz oben eine Drei, also darf in dieser Spalte keine weitere
Drei sein.
Folglich bleibt für Drei
nur die dritte Spalte übrig.
|
Die erste Ziffer, die normalerweise
zuerst untersucht wird, ist Eins.
... ... |
Hier liegen die drei Blöcke, die irgendwo zwei Einsen
enthalten, untereinander.
In der mittleren Spalte liegen oben und unten zwei Blöcke
mit einer Eins. Also muss die mittlere Block in der rechten Spalte eine
Eins tragen.
Da sind zwei Kästchen möglich.
Man kann in diese beiden Kästchen zwei kleine Einsen
als Kandidaten schreiben. Das ist eine hilfreiche Notiz für später
und man hat das befriedigende Gefühl etwas zu tun.
|
Suche nach einer Zwei
... |
Die Zwei kommt zwar zweimal vor, nicht aber in Blöcken
einer Reihe oder Spalte.
Deshalb führt das Scannen zu keinem Ergebnis.
|
Suche nach einer Vier
... |
Auch für die Vier führt das Scannen nicht weiter.
|
Suche nach der Fünf
... |
Eine Fünf ergibt sich
eindeutig.
|
Die gefundene Fünf hat Folgen:
... ... |
Mit Hilfe dieser Fünf wird die Lage einer weiteren
Fünf auf drei Kästchen eingeengt.
|
Suche nach einer Sechs
Suche nach einer Sieben
... |
Eine vergebliche Suche!
|
Suche nach einer Acht
Man findet also drei Achten.
... ... |
Die letzte gefundene Acht
liegt in einem Kästchen mit einer kleinen Sechs.
Da dieses Kästchen jetzt mit einer Acht besetzt ist,
kommt in das andere Kästchen eine Sechs.
|
Das wiederum hat Konsequenzen.
... |
|
Es ergeben sich zwei weitere Sechsen.
Damit sind alle Sechsen gefunden. |
Zurück zur Suche nach einer Acht
... ... |
Da in der ersten Zeile im mittleren Block eine Acht steht,
muss in der zweiten Zeile ganz rechts eine Acht
stehen.
Damit sind alle Achten gefunden.
|
Suche nach einer Neun
Zwischenbilanz
... |
Mit dem Scannen sind also zehn Ziffern gefunden.
30 Ziffern waren gegeben, jetzt sind 40 Ziffern bekannt.
|
In einem zweiten Durchgang
durchforste ich die einzelnen Blöcke. Am besten beginnt man mit einem
Block, die schon möglichst viele Ziffern enthält, zum Beispiel
mit dem Block oben in der Mitte. Man geht die fehlenden Ziffern Zwei, Drei
und Vier durch.
Der nächste Block liegt
unten rechts. Da fehlen noch Eins, Drei und Vier.
Weiter
Zurück zum Block unten rechts
Der nächste Block, der
untersucht werden soll, liegt links in der Mitte.
Das brachte nicht viel.
In einer Erweiterung
werden an Stelle von weiteren Blöcken auch Zeilen oder Spalten einzeln
untersucht.
In der ersten Spalte fehlen nur noch zwei Ziffern, nämlich
Zwei und Drei.
Sie können leicht bestimmt werden, und man gelangt
schrittweise weiter bis zur endgültigen Lösung dieses Sudokus.
Es folgt eine Fleißarbeit.
Die meisten einfachen Sudokus
kann man mit den bisher beschriebenen Techniken lösen. Man kann diese
mit der "Suche nach Singles" zusammenfassen. Bei vielen Sudokus reicht
diese Technik aus.
Lösen
eines schweren Sudokus top
... ... |
Bei einem England-Aufenthalt versuchte ich mich an dem
Sudoku Nr. 125 (hard) der Tageszeitung "The Guardian" vom 30.09.2005.
Gegeben sind nur 25 Ziffern.
Man beachte wieder die Symmetrie in den gegebenen Ziffern.
|
... ... |
Mit dem Verfahren "Suche nach Singles" konnten 14 Ziffern
gefunden werden.
|
Dann ging es nicht mehr weiter.
... ... |
So machte ich mich an die mühselige Arbeit, für
jedes Kästchen alle möglichen Ziffern zu notieren. Das ist die
sogenannte Kandidatenliste. Man erhält sie, indem man jedes freie
Kästchen auf alle möglichen Ziffern hin untersucht und die Kandidaten
einträgt. (Die Kandidaten fand ein Programm.)
|
Die rote Neun und die rote Sechs kann man noch streichen:
In den Blöcken oben müssen untereinander zwei
Neunen und zwei Sechsen stehen, da das die einzigen Möglichkeiten
sind. Dann müssen sie unten (rot) in der fünften Zeile wegfallen.
Man spricht hier von der Methode gerichteter Paare (pointed
pairs).
Das half allerdings nicht weiter.
So glaubte ich, eines dieser Sudokus vor mir zu haben,
das man nicht allein durch logisches Schließen, sondern nur durch
Fallunterscheidungen lösen kann (1).
Ich setzte zum Beispiel in das gelbe Kästchen einmal
die Vier, einmal die Drei ein.
... ... |
Setzt man oben eine Vier ein, so findet man nach etlichen
Schritten Zwei und Drei (rot) in der Kachel unten rechts. Aber das (rote)
Kästchen, in dem eine dieser Ziffern stehen muss, bleibt leer.
Das ist ein Widerspruch.
|
... ... |
Setzt man in das gelbe Kästchen eine Drei, so erhält
man die restlichen Ziffern als Singles.
Dieses ist die Lösung.
|
Das Sudoku ist aber gar nicht
ein Sudoku, das nur durch Fallunterscheidungen zu lösen ist.
Das zeige ich im nächsten Kapitel.
Einsatz von Programmen
top
Das Lösen von Sudokus durch Probieren ist unbefriedigend.
Deshalb setzte ich auf das letzte Sudoku einige Programme aus dem Internet
an, die logisch vorgehen und den Weg auch zeigen. Und siehe da, es stellte
sich heraus, dass ich mindestens drei Einstiege zu einem weiteren Lösungsweg
übersehen hatte. Das Sudoku war gar nicht ein Sudoku, das nur durch
Fallunterscheidungen zu lösen ist.
Das erste Programm "Simple Sudoku" (URL unten) gab eine
Drei
oben in der achten Spalte an.
Dieses ist der Gedankengang.
... ... |
In der Kachel unten links besetzen die Paare 24 und 24
in der zweiten Spalte zwei Kästchen. Also kann man die rote Zwei in
der rechten unteren Ecke der Kachel streichen.
In der Kachel unten rechts besetzen die Paare 23 und 23
zwei Kästchen.
Also muss die Drei unten im gelben Kästchen wegfallen
und erscheint oben in der achten Spalte.
|
Das Online-Programm von Scanraid
(URL unten) fand noch ein rote
Neun in der
vierten Spalte und sechsten Zeile.
Das ist die Begründung.
... ...
|
Zum linken Quadrat:
In den oberen Kacheln liegen die Neunen in der dritten
und sechsten Spalte. Deshalb kann die Neun nur noch in der vierten Spalte
(grün) stehen. Das Verfahren heißt X-Wing-Technik.
Zum rechten Quadrat:
In den mittleren Kacheln muss Neun in einem gelben Kästchen
in der zweiten und siebten Spalte liegen. Also bleibt für die Neun
nur das Kästchen in der vierten Spalte. Wieder ist es die X-Wing-Technik. |
Eine weitere Ziffer, die
das gleiche Programm als nächstes angab, ist die Sieben.
Dabei wird die Neun von oben in der vierten Spalte gar nicht verwendet.
... ...
|
In der gelben Spalte müssen die Ziffern 6 und 9
in der rechten mittleren Kachel vorkommen. Dann ist dort kein Platz mehr
für die Sieben.
Das ist das Verfahren der versteckten Paare ("hidden
pairs")
Also muss die Sieben oben stehen.
Die restlichen Ziffern ergeben sich dann problemlos wie
im ersten Beispiel.
Dieser Weg wird hier nicht weiter dargestellt.
|
Es ist auch möglich,
die rote Sieben in der 7. Spalte mit Hilfe der Methode der "directed pairs"
zu sichern: Im Block unten rechts liegen die Paare 23, also ist oben die
Drei zu streichen und die Sieben bleibt. Darauf wies Michael Alfers hin.
Auf dieser Seite werden zum
Lösen verschiedene Techniken u.a. angewandt:
>das Scannen
>die Suche nach versteckten Singles
>die Methode der gerichteten Paare
>die Methode der versteckten Paare
>die X-Wing-Technik.
Es gibt noch weitere Techniken. Noch sind ihre Bezeichnungen
nicht einheitlich.
Die meisten Programme geben nicht sofort die vollständige
Lösung an, sondern verwenden nacheinander die einzelnen Verfahren
und nennen die Suchtechnik.
Ich habe auf dieser Seite nicht Programme ins Spiel gebracht,
um das Lösen mit Programmen zu empfehlen. Im Gegenteil, Sudoku kann
man gut mit primitiven Mitteln (Bleistift, Radiergummi und Papier) lösen
und ist dann nicht an den Computer gebunden.
Aber ehe man aufgibt, sollte man vielleicht die Computer
nach dem nächsten Schritt befragen und so dazulernen.
Versuch und Irrtum
top
Zum Schluss noch ein Sudoku, das nur durch Fallunterscheidungen
zu lösen ist (Stand April 2008).
... ... |
Es stammt aus dem ersten Band der Sudoku-Reihe von Die
Zeit/Handelsblatt (2).
Dieses Sudoku hat die Nummer 138.
Gegeben sind 24 Ziffern, die wieder symmetrisch angeordnet
sind.
|
... ... |
Das Programm "Simple Sudoku" erreicht durch logisches
Schließen das Stadium links. Dann wird vorgeschlagen, es in der 4.Spalte
und 5.Zeile mit der Neun zu versuchen.
Das führt dann zur Lösung.
Das Programm Scanraid erreicht fast den gleichen Zustand
und meldet dann:
"Run out of known strategies." |
Stand Januar 2009:
Scanraid kann jetzt auch dieses Sudoku mit einer neuen
Technik lösen. Das ist mir zu kompliziert.
Varianten top
4x4 und 6x6
Sudoku kann auch auf anderen Feldern gespielt werden.
Sudokus auf kleinen Feldern sind einfacher zu lösen.
Sie heißen dann auch "Sudokus für Kids"
Die schwarzen Ziffern waren gegeben, die roten wurden gefunden.
Mehr zum Beispiel auf der Seite sudokuweb.org (URL unten)
Sudoku im Internet
top
Deutsch
Otto Janko
Sudoku
Spektrum der Wissenschaft
Schwerer
als Sudoku: Euler'sche Quadrate
Vincke & Steiner OG
Sudoku-Löser
Wikipedia
Sudoku,
Lateinisches
Quadrat
Englisch
Angus Johnson
Simple Sudoku
(program)
Chris Hogg (BBC)
'Father
of Sudoku' puzzles next move
Michael Mepham:
Solving
Sudoku (.pdf-Datei)
SudokuWiki.org (Andrew Stuart)
Sudoku
Solver
Sudokulist
Sudoku
Torsten Sillke
Metapuzzle
involving NUMBER PLACE Puzzles
Wikipedia
Sudoku,
Mathematics
of Sudoku, Latin
Square
Kommentar top
Wie so oft in meiner Homepage nenne ich auch hier Torsten
Sillke als sachkundigen Ratgeber. Er hat sich schon 1998 mit Sudokus beschäftigt,
als sie offenbar nur in Japan populär waren. Auf seiner Seite (URL
oben) nannte er sie "NUMBER PLACE Puzzles", erwähnt aber am Ende seiner
Dokumentation schon den japanischen Namen Sudoku.
Referenzen top
(1) Michael Mepham: Sudoku. Das spannendste Zahlenrätsel
der Welt, Knaur München, 2005
(2) Die Zeit (Hg.) Handelsblatt (Hg.): Sudoku, Frankfurt
am Main 2005 [ISBN3-596-17180-6]
(3) Die Zeit (Hg.) Handelsblatt (Hg.): Sudoku für
Profis, Frankfurt am Main 2005 [ISBN3-596-17225-X]
Feedback: Emailadresse
auf meiner Hauptseite
URL meiner
Homepage:
https://www.mathematische-basteleien.de/
©
2005 Jürgen Köller
top |
