Erfahrungen mit Sudokus
Inhalt dieser Seite
Was ist Sudoku?
Lösen eines leichten Sudokus
Lösen eines schweren Sudokus
Einsatz von Programmen
Versuch und Irrtum
Varianten
Sudoku im Internet
Kommentar
Referenzen
.
Zur Hauptseite    "Mathematische Basteleien"

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 QuadratSudoku



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