|
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 sicher 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 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.
Näheres später.
Varianten top
9x9
Ed Pegg Jr. hat Varianten des Sudokus auf dem 9x9-Feld zusammengestellt
(URL unten).
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.
Vegard Hanssen gibt auf seiner Website (URL unten) viele Formate an.
Sudoku im Internet top
Deutsch
Die Zeit
Sudoku
Otto Janko
Sudoku
Uwe Wiedemann
Sudoku-Varianten und andere Puzzles
Spektrum der Wissenschaft
Schwerer
als Sudoku: Euler'sche Quadrate
Wikipedia
Lateinisches
Quadrat, Sudoku
Englisch
Angus Johnson
Simple Sudoku (program)
Ed Pegg (MAA Online)
Sudoku
Variations
Gerard Roomer
Sudokusite
Scanraid Ltd
Sudoku Solver
(Online-Programm)
Sudokulist
Sudoku
Michael Mepham: Solving
Sudoku (.pdf-Datei)
The "unsolvable"
sudoku
Torsten Sillke
Metapuzzle
involving NUMBER PLACE Puzzles
Uwe Wiedemann
Sudoku Variants and
other puzzles
Vegard Hanssen
Sudoku Puzzles 6x6
Wikipedia
Latin Square,
Sudoku,
Mathematics
of Sudoku,
Japanische Seite in Englisch:
NIKOLI Co.,Ltd
web Nikoli
- Why we are keeping to make Sudoku by hand?
- How to make Sudoku
- Do you know history of Sudoku?
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:
http://www.mathematische-basteleien.de/
©
2005 Jürgen Köller
top |
