away from the sun...

Ein Sûdoku-Rätsel



Beschreibung
Das Puzzlefeld besteht aus einem Quadrat, das in 3 × 3 Unterquadrate bzw. Blöcke eingeteilt ist. Jedes Unterquadrat ist wieder in 3 × 3 Felder eingeteilt, sodass das Gesamtquadrat also 81 Felder (= 9·9 Felder) bzw. 9 Reihen und 9 Spalten mit je 9 Feldern besitzt.

In einige dieser Felder sind schon zu Beginn Ziffern (1 bis 9) eingetragen. Typischerweise sind 22 bis 36 Felder von 81 möglichen vorgegeben. Das Puzzle muss nun so vervollständigt werden, dass

in jeder Zeile,
in jeder Spalte und
in jedem der neun Blöcke jede Ziffer von 1 bis 9 genau einmal auftritt.
Inzwischen gibt es auch Sûdokus mit 4 × 4 Unterquadraten und somit 256 (= 16·16) Feldern, in die 16 verschiedene Zahlen, Buchstaben oder Symbole verteilt werden. Ebenso sind 5 × 5 Sûdokus denkbar, etc. Für Kinder gibt es Sûdokus mit einer Kantenlänge von 2 pro Unterquadrat, also werden dort nur 4 Ziffern oder Bildsymbole benötigt. Eine weitere Variante sind Sudokus mit treppenförmiger Begrenzung der Blöcke (engl. Stairstep Sudoku).

Seit Ende 2005 gibt es tragbare, elektronische Sudoku-Geräte.

Ursprung
Das heutige Sudoku stammt aus den USA. Dort wurde es 1979 in der Zeitschrifft Math Puzzels & Logic Problems erstmals publiziert. Seinen Durchbruch erlangte das Sûdoku jedoch erst um etwa 1984, als die japanische Zeitschrift Nikoli diese zunächst unter dem Namen Suji wa dokushin ni kagiru regelmäßig abdruckte. Hieraus entwickelte sich schließlich der Begriff Sûdoku. Der Neuseeländer Wayne Gould hat Sûdoku auf einer Japanreise kennen gelernt. Sechs Jahre brauchte er, um eine Software zu entwickeln, die neue Sûdokus per Knopfdruck entwickeln kann.

Anschließend bot er seine Rätsel der „Times“ in London an. Die Tageszeitung druckte die ersten Sûdoku-Rätsel und trat auf diese Weise eine Sûdoku-Lawine in der westlichen Welt los. Inzwischen haben schätzungsweise 100 Millionen Menschen weltweit mindestens eine Partie Sûdoku gespielt, heißt es.

In Österreich führte der regelmäßige Abdruck in Tageszeitungen wie "Der Standard" und "Kronen Zeitung" zu einer raschen Verbreitung Ende 2005. Des weiteren erscheint es regelmäßig in der Hersfelder Zeitung.

Ein ähnliches Rätselspiel wurde unter dem Namen „Carré latin“ (Lateinisches Quadrat) vom Schweizer Mathematiker Leonhard Euler im 18. Jahrhundert erfunden; im Gegensatz zu Sûdoku ist dieses nicht in Blöcke (Unterquadrate) unterteilt.

Die Zahl der möglichen 9×9-Sudokus beträgt nach Berechnung von Bertram Felgenhauer (im Jahr 2005) 6.670.903.752.021.072.936.960; diese Zahl ist gleich 9! × 722 × 27 × 27.704.267.971; der letzte Faktor ist eine Primzahl.






Algorithmus
Belegung des gelösten Puzzles erstellen
1. Weg: Ein leeres Puzzlefeld wird Zelle für Zelle durch "Auswürfeln" (Zufallsgenerator) mit Ziffern befüllt. Sobald es zu einem Regelverstoß kommt, muss per Backtracking-Methode eine andere Belegung probiert werden. Dies ist weniger trivial als beim Lösen des Puzzles: Da eine möglichst "zufällige" Belegung des Puzzlefeldes benötigt wird, kann man nicht einfach alle Ziffern der Reihe nach durchprobieren. Es hindert aber nicht, alle Ziffern, sobald sie einmal "ausgewürfelt" wurden, als künftig - für die jeweilige Zelle - gesperrt "abzuhaken" (in einer Tabelle zu markieren)
2. Weg: Neun Einsen ohne Regelverstoß im Puzzelfeld verteilen. Dann neun Zweier, neun Dreier, usw. verteilen. Auch hier muss ein Backtracking-Algorithmus angewandt werden.
3. Weg: Man füllt eine Zeile oder eine Spalte in beliebiger Reihenfolge mit den erlaubten Ziffern, verschiebt dann mit jeder weiteren Zeile/Spalte die Ziffernfolge, bis man am Schluss alle möglichen Varianten untereinander/nebeneinander in einer n x n Matrix vorliegen hat. Dies alleine wäre ein äußerst trivial zu lösendes Rätsel, da sich die Ziffernfolgen wiederholen, deswegen sollte man über erlaubte Transformationen diese Matrix nun schrittweise so verändern, dass die Ursprungsziffernfolge sowie die ausgeführten Transformationen nicht mehr nachvollziehbar sind. Erlaubte Transformationen sind z.B. das Invertieren, das Spiegeln (vertikal, horizontal, schräg), Rotieren, Vertauschen ganzer Zeilen oder Spalten, sofern sie innerhalb eines Mini-Quadrates bleiben, - oder das Vertauschen ganzer Zeilen und Spalten von Miniquadraten. Etliche dieser Transformationen hintereinander verwischen (fast) alle Hinweise auf die ursprüngliche Ziffernfolge. Von den hier vorgestellten Erstellungsmethoden ist diese die am wenigsten aufwendige und rechenintensive.
Zur Lösung passendes Sudoku-Rätsel erzeugen
Wiederum durch "Auswürfeln" werden je nach Schwierigkeitsgrad zwischen 45 und 57 Ziffern wieder entfernt. Ohne weitere Kontrolle kann es hierbei passieren, dass das Puzzle trivial (langweilig) oder nicht mehr eindeutig lösbar wird.










Quelle: Wikipedia
Gratis bloggen bei
myblog.de