SudokuAnleitung2 (PDF)

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

Erfahrungen mit Sudokus
Inhalt dieser Seite
Was ist Sudoku?
Varianten
Lösen eines leichten Sudokus
Sudoku im Internet
Lösen eines schweren Sudokus
Kommentar
Einsatz von Programmen
Referenzen
Versuch und Irrtum
.
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.

1 von 13

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

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.

2 von 13

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

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

3 von 13

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

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

4 von 13

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

..
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
5 von 13

..

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

...
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.

6 von 13

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

Die meisten einfachen Sudokus kann man mit den bisher beschriebenen

7 von 13

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

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.
...

8 von 13

...

14.01.2015 22:22

Sudoku

http://www.mathematische-basteleien.de/sudoku.htm

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-WingTechnik.
Zum rechten Quadrat:
In den mittleren Kacheln muss Neun
in einem gelben Kästchen in der
...
zweiten und siebten Spalte liegen.

9 von 13

14.01.2015 22:22