Sudoku

aus Wikipedia, der freien Enzyklopädie

Sudoku (jap. 数独 Sūdoku, kurz für 数字は独身に限る Sūji wa dokushin ni kagiru, wörtlich „Zahlen als Einzel beschränken“) ist ein Logikrätsel und ähnelt Magischen Quadraten. In der üblichen Version ist es das Ziel, ein 9x9 Gitter mit den Ziffern 1 bis 9 so zu füllen, dass jede Ziffer in einer Spalte, in einer Reihe und in einem Block (3x3 Unterquadrat) nur einmal vorkommt. Ausgangspunkt ist ein Gitter, in dem bereits mehrere Ziffern vorgegeben sind. In einer weltweit stark zunehmenden Zahl an Zeitungen und Zeitschriften werden heute regelmäßig Sudoku Rätsel veröffentlicht.

Ein Sūdoku-Rätsel

[Bearbeiten] Ursprung

Die frühesten Vorläufer des Sudoku waren die Lateinischen Quadrate des Schweizer Mathematikers Leonhard Euler, der solche unter dem Namen: „carré latin“ bereits im 18. Jahrhundert verfasste. Anders als die modernen Sudoku-Rätseln waren diese noch nicht in Blöcke (Unterquadrate) unterteilt.

Von 1892 bis zum Ausbruch des Ersten Weltkrieges publizierten die französischen Zeitungen Le Siècle und La France regelmäßig Rätselquadrate unter dem Titel: „Carré magique diabolique“. Diese frühen Publikationen setzten sich allerdings auf Dauer nicht durch. Ihnen fehlte ebenfalls die Unterteilung in Unterblöcke.

Das heutige Sudoku mit Einbeziehung der Blöcke (neben Zeilen und Spalten) wurde erstmals 1979 anonym von dem damals 74-jährigen Architekten und freischaffenden „Rätselonkel“ Howard Garns^[1] in der Zeitschrift Dell Pencil Puzzles & Word Games (engl. Bleistifträtsel & Wortspiele) als: „Number Place“ (engl. Zahl(en)platz) veröffentlicht.^[2] Er verstarb 1989, sodass er nicht erleben konnte, wie seine Kreation zu weltweiter Begeisterung führte.

Die ersten Sudokus wurden zwar in den USA publiziert, seinen Durchbruch erlebte das Zahlenrätsel jedoch erst irgendwann zwischen 1984 und 1986, als die japanische Zeitschrift Nikoli es zunächst unter dem Namen: „Sūji wa dokushin ni kagiru“ (数字は独身に限る) (svw.: die/alle Zahlen müssen (genau) einmal vorkommen) regelmäßig abdruckte. 1986 wurde diese sperrige Bezeichnung vom Herausgeber Maki Kaji unter Beibehaltung der jeweils ersten Kanji-Zeichen zu „Sudoku“ (数独; sūdoku) verkürzt und als Marke registriert, deshalb werden selbst heute noch diese Rätsel in manchen japanischen Zeitschriften unter dem engl. Begriff: „Number Place“ abgedruckt, auch die Bezeichnung als: „Nanpure“ (u. a. als Spiel für Sonys PlayStation) ist teilweise üblich.

Der Neuseeländer Wayne Gould lernte Sudoku auf einer Japanreise kennen und brauchte sechs Jahre, um eine Software zu entwickeln, die neue Sudokus per Knopfdruck entwickeln konnte. Anschließend bot er seine Rätsel der Times in London an. Die Tageszeitung druckte die ersten Sudoku-Rätsel und trat auf diese Weise in der westlichen Welt eine Sudoku-Lawine los.

In Österreich führte der regelmäßige Abdruck in Tageszeitungen wie Der Standard und Kronen Zeitung zu einer raschen Verbreitung Ende 2005. In Deutschland erscheinen Sudokus regelmäßig im Stern (2006), in der ZEIT und der mopo (2005), der Frankfurter Rundschau, im Der Tagesspiegel, in der Berliner Morgenpost, der Berliner Zeitung, der Hersfelder Zeitung , im Kölner Stadt-Anzeiger, in der Süddeutschen Zeitung und der Neue Presse aus Hannover.

Zum weltweiten Erfolg von Sudoku hat sicherlich beigetragen, dass das Prinzip des Rätsels nicht dem Urheberrecht unterliegt und somit keine Lizenzgebühren anfallen. Sudokus können jederzeit frei erstellt und veröffentlicht werden.

[Bearbeiten] Regeln und Begriffe

Das Spiel besteht aus einem Gitterfeld mit 3 × 3 Blöcken, die jeweils in 3 × 3 Felder unterteilt sind, insgesamt also 81 Felder in 9 Reihen und 9 Spalten. In einige dieser Felder sind schon zu Beginn Ziffern zwischen 1 und 9 eingetragen. Typischerweise sind 22 bis 36 Felder von 81 möglichen vorgegeben.

Ziel des Spiels ist es nun, die leeren Felder des Puzzles so zu vervollständigen, dass in jeder der je neun Zeilen, Spalten und Blöcke jede Ziffer von 1 bis 9 genau einmal auftritt.

Wenn eine Zahl in einem Feld möglich ist, bezeichnet man sie als „Kandidat“. Die drei Bereiche (Reihe, Spalte, Block) werden zusammengefasst als „Einheiten“ bezeichnet.

Obwohl Sudokus in der Regel mit Ziffern arbeiten, sind zur Lösung keinerlei Rechenkenntnisse erforderlich; man könnte ebenso neun andere abstrakte Symbole verwenden – Ziffern ermöglichen durch ihre feste und bekannte Reihenfolge jedoch ein leichteres Überprüfen der fehlenden Elemente innerhalb einer Einheit.

[Bearbeiten] Varianten

X-Sudoku (Musterbeispiel)

„X-Sudoku“ ist eine Variante, bei der zusätzlich zu den üblichen Sudoku-Regeln auch die beiden Diagonalen aus lauter verschiedenen Einträgen bestehen müssen. Der Name kommt daher, dass die beiden Diagonalen wie der Buchstabe X aussehen. Die Abbildung unten rechts zeigt ein X-Sudoku mittlerer Schwierigkeitsstufe. Im Idealfall hat diese Variante keine zusätzliche Lösung nach normalen Sudoku-Regeln - das „X“ sollte die einzige mögliche Lösung sein. Sudoku- und andere Rätsel-Zeitschriften veröffentlichen regelmäßig X-Sudokus in verschiedenen Größen, außer der Standardgröße 9×9 kommen auch andere Größen vor, etwa 8×8 (mit 2×4-Blöcken); in diesem Fall haben die beiden Diagonalen kein gemeinsames Schnittfeld.

Inzwischen gibt es auch Sudokus – meist als „Fudschijama“ bezeichnet – mit 4×4 Blöcken und somit 256 (= 16×16) Feldern, in die je 16 verschiedene Zahlen, Buchstaben oder Symbole verteilt werden sowie erweiterte Sudokus mit 4×3 Blöcken mit 144 (also jeweils 12×12) Feldern und „Mini-Sudokus“ für Einsteiger mit 2×3 Blöcken mit 36 (also 6×6) Feldern. Auch andere Blockgrößen, wie z. B. 5×5 (= 625) oder gar 6×6 (= 1296 Felder) sind denkbar. Für Kinder gibt es 4×4 Sudokus mit einer 2er-Kantenlänge pro Block, dabei werden also nur 4 Ziffern oder Bildsymbole benötigt.

Eine Variante erfreut sich seit Anfang 2006 unter dem Namen „Samurai“ steigender Beliebtheit: fünf Standard-Sudokus sind überlappend X-förmig angeordnet – eines zentral und an jeweils einer der vier Ecken ein weiteres. Dabei teilt sich jedes dieser vier Eck-Sudokus genau einen der vier äußeren Eckblöcke des Zentral-Sudokus, dadurch ergeben sich insgesamt 369 Felder verteilt auf 41 Blöcke.

Weitere Varianten sind Sudokus mit treppenförmiger Begrenzung der Blöcke (engl. „Stairstep Sudoku“) und solche mit unregelmäßig geformten Blöcken.

Eine weitere Variante ist drei-dimensional und heißt Roxdoku. Ein Roxdoku besteht aus 3*3*3 Würfelchen als Felder (in der Grundform). Hier darf nicht nur in Zeilen und Spalten, sondern auch in Ebenen keine Zahl/Buchstabe doppelt sein. Außerdem ist es auch hier, so wie in der 2D Version, möglich mit 4*4*4 Würfelchen oder gar noch mehr (5*5*5,...) zu spielen. Spielen kann man solche Roxdokus am Besten als Computerspiel, weil hier die Möglichkeit besteht das ganze „Spielfeld“ in alle Richtungen, so wie das für 3D-Objekte am Computer üblich ist, zu drehen.

Comparison Sudoku (Musterbeispiel)

Diese Variante erschien in Österreich (derStandard.at / LeichtSinn) am 2. August 2006 unter der Bezeichnung „Comparison Sudoku“ (engl. Vergleichs-Sudoku). In einem Comparison Sudoku werden keinerlei Zahlen vorgegeben, nur die Grenzlinien aller Einzelfelder jedes Blocks sind mit einer Ein- bzw. Ausbuchtung zu allen Nachbarfeldern hin versehen – im Sinne von < (kleiner als) oder > (größer als). Alle üblichen Sudoku Regeln gelten auch hier, allerdings müssen bei dieser Variante alle Zahlen durch Vergleiche gefunden werden. Jean-Paul Delahaye beschreibt diese Sudoku-Variante in Les ancêtres français du sudok (als Quelle wird die Zeitschrift Puzzler von 1999 genannt).^[3]

Kakuro wird häufig als Variante oder gar Nachfolger von Sudoku bezeichnet, ist jedoch faktisch ein eigenständiges Zahlenrätsel, das mit Sudoku nur den japanischen Ursprung gemein hat. Killer-Sudoku (auch: Sum Sudoku oder Samunamupure) verbindet Elemente von Kakuro und Sudoku; hier gibt es keine Schlüsselzahlen, sondern die Summe von Zahlen in zusammengefassten Gruppen wird angegeben.

Seit Ende 2005 gibt es tragbare elektronische Sudoku-Geräte. Des weiteren als einfaches Brettspiel und interaktiv online (Internet) sowie offline als Computerspiel.

[Bearbeiten] Lösungsmethoden

[Bearbeiten] Intuitives Raten

Intuitives Raten führt nicht zum Erfolg. Systematisches Vorgehen, genaue Analyse und logisches Denken sind gefordert. Nur so kommt man gesichert einen Schritt weiter und kann dann den nächsten Schritt darauf aufbauen. Leichtere Sudokus lassen sich in der Regel durch einfache logische Analysen lösen. Es kann aber auch sein und bei sehr schweren Sudokus ist dies meist der Fall, dass irgendwann ein Ausprobieren unvermeidbar wird. Aber auch dann sollte man nach einem System vorgehen.

[Bearbeiten] Analytisch-systematisch

Die Lösung eines Sudokus beruht auf mehreren Methoden, die miteinander zu kombinieren sind: Scannen, Auszählen, Kombination, Eliminierung und Hypothese. In erster Linie sollte über die logisch eindeutigen Methoden ein Weg gesucht werden. Die Hypothese verbleibt als letzte Konsequenz.

Im oberen rechten Block fehlt die Fünf. Durch Verfolgen der Fünfen in den zugehörigen Reihen und Spalten kann man Felder ausschließen. So bleibt nur eine Zelle (grün markiert) als einzig freie Möglichkeit für die Fünf übrig.

[Bearbeiten] Scannen

Scannen (auch: Kreuzschraffur, engl. cross-hatching) wird ganz am Anfang und während der weiteren Lösungssuche nach erfolgreichen Schritten mit den anderen Methoden stets erneut durchgeführt. Die Scan-Methode wird im nebenstehenden Bild erläutert. Der Reihe nach für alle Ziffern von 1 bis 9 werden die mit dieser Ziffer jeweils belegten Reihen und Spalten „gescannt“. Man erkennt dann, in welchem Block (oder auch Unterquadrat genannt), in dem diese Ziffer bisher fehlte, bei der Überkreuzung der Scans eindeutig nur eine Zelle als freie Position identifiziert werden kann. Für die schnellsten Resultate werden die Ziffern in der Reihenfolge ihrer Häufigkeit abgesucht. Falls man von einer Ziffer alle neun richtigen Zellen gefunden hat, kann man sich diese Ziffer auf einem Blatt notieren, um nachfolgend nicht unnötige erneute Scans mit dieser Ziffer zu wiederholen.

[Bearbeiten] Auszählen

Auszählen der fehlenden Ziffer in einem Block, einer Spalte oder einer Reihe (zusammen Einheit genannt). Es ist einleuchtend, dass dieses Verfahren umso erfolgreicher ist, je mehr Ziffern in der untersuchten Einheit bereits gefunden sind.

[Bearbeiten] Kombination

Bei der Kombination geht es darum, weitere logisch zwingende Zusammenhänge aufzudecken, die nach den obigen Methoden noch nicht herausgekommen sind. Es gibt hierzu mehrere Ansätze. Nehmen wir als Beispiel die 9 links oben in der zweiten Spalte. Auf den ersten Blick ist nicht erkennbar, wo sich die weiteren fehlenden 9en in den beiden darunter liegenden Blöcken befinden könnten. Im linken unteren Block kämen zunächst die beiden Zellen rechts oben sowie links oben infrage. Nun ist aber zwingend, dass im dazwischen liegenden mittleren Block eine 9 nur irgendwo in der dritten Spalte sein kann. Folglich ist die Zelle für die 9 im unteren Block an der Stelle links oben als eindeutiges Ziel gefunden und die 9 kann dort eingetragen werden. Grundsätzlich sind alle geschlossenen Dreier-Reihen bzw -Spalten eines Blocks ein Hinweis, dass eine derartige Kombination möglich sein könnte.

Im Prinzip handelt es sich hierbei um eine Variante der nachfolgend beschriebenen Eliminierungstaktiken. Allerdings wird für die hier aufgeführten Überlegungen noch kein Hilfsblatt - wie unten beschrieben - benötigt.

[Bearbeiten] Eliminierung

Bei der Eliminierung (oder: Kandidatenbeseitigung, Ausschluss, nackter Einer, naked single, lone number) geht es zunächst darum festzustellen, welche Kandidaten für eine Zelle überhaupt infrage kommen können. Als Hilfsmittel kann man sich das Ergebnis auf einem Blatt notieren, indem man je Zelle die möglichen Ziffern vermerkt. Man kann dies auch mit kleiner Schrift und Bleistift im Sudoku selbst notieren (siehe Kapitel: Hilfe beim Lösen). Wenn man feststellt, dass in einer Einheit (Reihe, Spalte oder Block) eine Kandidatenziffer nur einmal vorkommt, dann kann man diese Ziffer als Treffer eintragen. Bei der weiteren Eliminierung kommt man damit vorwärts, dass man mehrmals hintereinander Kandidatenziffern von einer oder mehreren Zellen beseitigt, um gerade noch eine Wahl zu lassen. Es gibt eine Vielzahl von Eliminierungstaktiken, die aber alle auf einfachen Regeln mit logisch eindeutigen Schlussfolgerungen basieren.

• So sucht man z. B. die Spalte, Reihe oder den Block mit den wenigsten Leerzellen heraus. Nimmt man in dem abgebildeten Sudoku beispielsweise die 5. Spalte. Hier fehlen 3, 4, 5. Nun vermerkt man mit Bleistift für jede freie Zelle dieser Spalte die anscheinend möglichen Ziffern. In der 3. Reihe also die 3 und die 4. In der 5. Reihe in der Mitte sind die Ziffern 3 und 4 nicht möglich, so dass hier nur die 5 stehen kann. Jetzt wird der Rest leicht, da in der 7. Reihe nur die 3 korrekt ist, und folglich in der 3. Reihe die 4 als Lösung verbleibt. Die Reihe ist nun komplett.
• Eine weitere Methode benutzt die notierten Kandidaten in einer Einheit. Wenn es sich z. B. ergibt, dass für zwei Zellen einer Einheit dieselben beiden Kandidatenziffern (und nur diese beiden) zutreffen, dann sind diese beiden Zellen eindeutige Treffer. Man weiß nur nicht, welche Zelle welche Ziffer beinhaltet. Wenn nun eine dieser beiden Kandidatenziffern auch bei einer weiteren Zelle dieser Einheit auftaucht, kann man sie dort von der Kandidatenliste streichen.

[Bearbeiten] Hypothese

Die Hypothese (oder: was-wäre-wenn?, Ariadnes Faden, Backtracking) sollte erst dann angewendet werden, wenn alle oben dargestellten Methoden nicht mehr weiterhelfen. Aber auch hier ist es hilfreich nicht wahllos vorzugehen. Wenn man sich nicht die Mühe machen will, die Hypothese auf einem getrennten Blatt auszutesten, kann man die eindeutigen Treffer mit Kugelschreiber und die hypothetischen Ziffern mit Bleistift eintragen, um die Ausgangssituation im Fall einer falschen Hypothese wiederfinden zu können. Für ein Ausprobieren eignen sich vor allem Zellen, die nur zwei mögliche Kandidaten aufweisen, weil dann eine falsche Hypothese die Alternative als richtig bestätigt. Auch ist es sinnvoll sich eine Zelle auszusuchen, die es erlaubt, anschließend wieder mit den obigen Methoden fortzufahren. Meist liegen diese Zellen mehr im Zentrum des Sudokus bzw in Räumen, die bereits vergleichsweise weit gelöst sind. Mehrstufige Hypothesenfolgen sind nur schwer zu lösen.

[Bearbeiten] Algorithmisch

Eine Methode zum Lösen eines Sudoku ist die Behandlung als Schnittmengenproblem. Aus den vorgegebenen Ziffern lässt sich für jedes Feld eine Menge von Kandidatenziffern bestimmen, die für ein Feld die Schnittmenge aus je drei Mengen ist: Diese sind die Komplemente der jeweils in derselben Zeile, Spalte und im selben Quadrat enthaltenen Ziffern zur Menge aller Ziffern (ohne die Null). In einfachen Fällen hat das Rätsel die Eigenschaft, dass mindestens ein Feld eine einelementige Kandidatenmenge besitzt, oder dass ein Element aus einer Kandidatenmenge eines Feldes nicht in den Kandidatenmengen aller anderen Felder derselben Spalte oder Zeile oder desselben Quadrats vorkommt. Dieser Kandidat kann dann fest in das jeweilige Feld eingesetzt werden und die betreffende Ziffer aus den Kandidatenmengen der übrigen Felder in derselben Zeile, Spalte und im selben Quadrat entfernt werden. Dieses Verfahren wird dann solange wiederholt, bis alle Zellen aufgefüllt sind.

• Ziffern
• Mengen der in je einer Zeile enthaltenen Ziffern
• Mengen der in je einer Spalte enthaltenen Ziffern
• Mengen der je in einem Teilquadrat enthaltenen Ziffern

Die Kandidatenmenge K_i,j eines Feldes F_i,j berechnet sich dann in jedem Iterationsschritt wie folgt:

Bei den meisten eindeutig lösbaren Rätseln, insbesondere den schwierigen, führt diese Methode allein nicht zur Lösung. In diesen Fällen müssen z. B. Paare oder Tripel von Kandidaten gemeinsam betrachtet werden, um die Kandidatenmengen in einem ersten Schritt zu verkleinern. Hierbei werden logische Verknüpfungen zwischen mehreren Feldern gesucht, von denen klar ist, dass bestimmte Zahlen in den Feldern dieser Gruppe stehen, wodurch diese Zahlen für die nicht in der Gruppe befindliche als Lösungen ausscheiden (Beispiel: {1, 2} {2, 3} {3, 1}; wenn diese Kandidatenmengen z. B. in einer Reihe stehen, ist klar, dass diese Gruppe die Zahlen 1, 2 und 3 enthalten muss, wodurch sie aus allen anderen Kandidatenmengen in dieser Reihe ausscheiden). Alternativ kann, falls in einem Iterationsschritt keine einelementige Kandidatenmenge existiert, aus einer der (kleinsten) Kandidatenmengen eine Zahl ausgewählt werden, um eine der mehreren möglichen Lösungen zu erhalten (Versuch-und-Irrtum-Methode). In Lösungsprogrammen wird diese Methode wohl am häufigsten zu finden sein, da es in den meisten Fällen am Ende ökonomischer ist, die Brute-Force-Methode einzusetzen, als alle Felder auf Untergruppen zu überprüfen.

[Bearbeiten] Nach der Backtracking-Methode

Auf dem Computer kann man ein Sudoku mit der Backtracking-Methode lösen. Beginnend mit dem ersten freien Feld, probiert man systematisch, mit der Eins beginnend, ob man zu einer Lösung kommt. Beim ersten Widerspruch geht man zurück (engl. backtrack). Dieser Lösungsweg lässt sich sehr elegant rekursiv formulieren, und man ist sicher, dass alle Kombinationsmöglichkeiten abgesucht werden. Da es sich um tausende Wege handeln kann, ist dieser Algorithmus nur für Computerprogramme geeignet. Der Lösungsalgorithmus ist allerdings bestimmt nicht der Schnellste, da er keinerlei analytische Vorinformationen verwendet und nur durch Ausprobieren vorgeht. Dennoch erhält man auf gewöhnlichen PCs auch für schwierige 9x9-Sudokus die Lösung innerhalb einer Sekunde. Bei größeren Sudokus stößt die Backtracking-Methode jedoch schnell an ihre Grenzen. Da dieses Problem NP-vollständig ist^[4] lassen sich beliebig große Sudokus praktisch nicht mit dem Computer lösen, weil die Laufzeit exponentiell mit der Problemgröße anwächst.

[Bearbeiten] Erstellung neuer Sudokus

Schwieriger als das Lösen eines Sudoku ist deren Erstellung.

• Eindeutige Lösung: Es darf nur eine korrekte Lösung existieren.
• Gewünschter Schwierigkeitsgrad: Die Anzahl der vorgegebenen Ziffern bestimmt nicht allein den Schwierigkeitsgrad. Die Anordnung spielt eine entscheidende Rolle.

[Bearbeiten] Algorithmus

1. 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 × 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 Spiegeln (vertikal, horizontal, schräg), das Rotieren, das 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 aber rechenintensivste.
   • 4. Weg: Aus einem vorhanden Sudoku durch Transformation ein „neues“ Sudoku erstellen. Mögliche Transformationen sind etwa das Drehen und Spiegeln des Brettes, die Vertauschung von Zeilen innerhalb eines Blocks oder von ganzen Blöcken, sowie das elementweise Anwenden von Permutationen.
2. Zur Lösung passendes Sudoku-Rätsel erzeugen
   • Wiederum durch „Auswürfeln“ werden je nach Schwierigkeitsgrad eine Anzahl Ziffern wieder entfernt (typischerweise so dass zwischen 22 und 36 Ziffern verbleiben). Ohne weitere Kontrolle kann es hierbei aber passieren, dass das Puzzle trivial (langweilig) oder nicht mehr eindeutig lösbar wird.

[Bearbeiten] Mathematik

Die Zahl der möglichen 9 × 9-Sudoku-Lösungen beträgt nach Berechnung von Bertram Felgenhauer (im Jahr 2005) 6.670.903.752.021.072.936.960. Diese Zahl ist gleich 9! · 72² · 2⁷ · 27.704.267.971 (der letzte Faktor ist eine Primzahl). Durch triviale Umformung kann diese Konstante in die Finis-Normalform^[5] überführt werden, die in diesem Fall sogar einer Primfaktorzerlegung gleich kommt: 7 · 5 · 3⁸ · 2²⁰ · 27.704.267.971. Die Zahl wurde unabhängig davon durch Ed Russell bestätigt. Nach Ed Russell und Frazer Jarvis gibt es 5.472.730.538 Möglichkeiten bei Berücksichtigung von Symmetrien. Die Zahl gültiger 16 × 16-Sudokus ist unbekannt.

Die maximale Zahl von Vorgaben, die nicht zu einer eindeutigen Lösung führen, ist, unabhängig von der Variante, um vier geringer als die Gesamtzahl der Felder (z.B. 81 - 4 = 77 bei der Standardvariante). Wenn von zwei Zahlen jeweils zwei Vorgaben fehlen, die zugehörigen Felder auf den Ecken eines Rechtecks liegen, dessen Ecken paarweise im selben Block liegen und dessen Kanten in der selben Zeile bzw. Spalte liegen, gibt es zwei Möglichkeiten, diese Zahlen einzutragen. Das andere Extrem – die Mindestzahl von Vorgaben, die zu einer eindeutigen Lösung führen – zu bestimmen, ist ein ungelöstes Problem. Die Mindestzahl, die bisher für die Standardvariante ohne Symmetrieforderung gefunden wurde, ist 17. Dies haben japanische Rätselenthusiasten herausgefunden. Bei drehsymmetrischer Anordnung sind es 18.

Hier ein Beispiel für ein Sudoku mit 17 vorbelegten Feldern.

[Bearbeiten] Hilfen beim Lösen

Die Hilfen zum Lösen eines Sudokus sind nicht normiert. Deshalb werden hier nur Hilfen angeboten, die jeder individuell abändern und verfeinern kann.

[Bearbeiten] Die „Uhrzeigerstrichmethode“

Da die Sudokus in Zeitungen und Magazinen häufig sehr klein abgedruckt sind, ist die Uhrzeigerstrichmethode hilfreich, die Kandidaten für ein Feld festzuhalten. Man macht im Feld einen kleinen Strich an der Stelle des „Uhrzeigers“ (siehe Bild). Die Fünf stellt eine Ausnahme dar; sie wird als kleiner Punkt in der Mitte dargestellt. So kann man sich mehrere Kandidaten für ein Feld merken. Wenn man keinen Radiergummi zur Hand hat, kann man einen Kandidatenstrich einfach durchstreichen, wenn weitere Überlegungen diesen ausschließen. Diese Methode ist bei weitem leserlicher als das Schreiben von kleinen Zahlen.

Anstelle der im Uhrzeigersinn umlaufenden Striche kann man auch sehr gut nur Punkte setzen und zwar beginnend für die Eins in der linken oberen Ecke. Oben in der Mitte kommt der Punkt für eine Zwei, in der rechten oberen Ecke der Punkt für eine Drei, am linken Rand in der Mitte liegt der Punkt für eine Vier und so weiter bis zum Punkt für eine Neun, der dann in der rechten unteren Ecke steht. Damit braucht man für die Fünf auch keine Ausnahme zu machen, der Punkt für sie kommt nach diesem System sowieso in die Mitte.

[Bearbeiten] Unsichere Zahlen markieren

„Zahlen trage ich nur mit Bleistift ein, um sie notfalls wieder wegradieren zu können. Eine unsichere Zahl markiere ich mit einem Sternchen, alle nachfolgenden dann mit einem Punkt. Taucht später ein Fehler auf, kann ich alle markierten Zahlen wegradieren und an der Sternchen-Stelle neu ansetzen“, empfiehlt Kerstin Wöge aus Spandau, die erste Sudoku-Meisterin, in der BZ vom 29. November 2005.

[Bearbeiten] Papierstreifen

Man kann sich auch zwei bis drei Papierstreifen zuschneiden. Mit diesen kann man gleiche Zahlen abdecken. Am besten geht man die Zahlenreihe immer wieder von 1 bis 9 durch. Das erleichtert das Ausfüllen ungemein, da man vom Zahlengewirr nicht abgelenkt wird. Ist man etwas geübter im Umgang mit den Papierstreifen, kann man auch einen Bleistift verwenden.

[Bearbeiten] Negativraster

Beim Negativraster werden die leeren Felder in neun Hilfsfelder aufgeteilt. Jedem der Hilfsfelder wird eine Zahl zugeordnet. Durch Auskreuzen der nicht möglichen Zahlen ergibt sich eine bessere Übersicht über die möglichen Zahlen.

[Bearbeiten] Weltmeisterschaft

Vom 10. bis 12. März 2006 wurden in Lucca (Italien) die ersten offiziellen Sudoku-Weltmeisterschaften durchgeführt. Initiator war der Mailänder Verlag Nonzero, Teilnehmer waren 85 Kandidaten aus 22 Nationen. Weltmeisterin wurde die tschechische Wirtschaftswissenschaftlerin Jana Tylova, den zweiten und dritten Platz belegten mit dem Chemiestudenten Thomas Snyder und dem Softwareentwickler Wei-Hwa Huang zwei US-Amerikaner. Auch vier Deutsche nahmen an der Meisterschaft teil: die drei Siegerinnen und Sieger der deutschen Sudoku-Meisterschaft 2005 sowie Kopfrechnen-Weltmeister Gert Mittring, der von RTL ins Rennen geschickt wurde, aber als Drittletzter sehr schlecht abschnitt.

Die Weltmeisterschaft 2007 wird vom 28. März bis zum 1. April in Prag stattfinden. Die deutschen Teilnehmer wurden auf der deutschen Meisterschaft am 4. November 2006 in Hamburg ermittelt. Die Qualifikation für die deutsche Meisterschaft fand am 21. Oktober statt. Infos dazu finden sich im Internet unter http://www.stern.de/dsm und http://www.logic-masters.de/index.php?page=dsm .

[Bearbeiten] Literatur

• Bach, Claudia: Sudoku-Trick-Kiste. AEGIS GmbH. Berlin, 2006. ISBN-13: 978-3-9811369-1-3. Die erste umfassende Darstellung in Buchform von Lösungsstrategien, wie sie sonst nur in Internetforen bekannt sind. Aktualisierungen zum Buch erfolgen auf der Internetseite der Autorin.
• Bird, Richard: How to write a functional pearl, invited talk der ICFP 2006. Ein einfacher Sudoku Löser in Haskell, clever algebraisch hergeleitet.
• Blum, Wolfgang: NEUN ZIFFERN GEGEN EINEN. SZ WISSEN. 12/2006. Seite 42 - 51. Artikel ist derzeit noch im Internet verfügbar: http://www.sueddeutsche.de/,Ple4Lar/wissen/artikel/191/89102/
• Delahaye, Jean-Paul : Sudoku oder Die einsamen Zahlen. In: Spektrum der Wissenschaft, März 2006, [p. 100–106] ISSN 0170-2971

[Bearbeiten] Weblinks

Commons: Sudoku – Bilder, Videos und/oder Audiodateien

Wikibooks: Sudoku – Lern- und Lehrmaterialien

• Sudoku als Brettspiel - Übersichtsartikel der Zeitschrift Spielbox
• Lösungsanleitung (PDF, englisch)
• Links zum Thema „Sudoku-Online“ im Open Directory Project
• Sudoku-Varianten der ersten Sudokuweltmeisterschaft (PDF, englisch)
• Sudoku als Thema im Unterricht (im ZUM-Wiki)
• Der Rätsel-Verein Logic Masters Deutschland e.V. führt die Deutschen Sudoku Meisterschaften durch.

[Bearbeiten] Quellen

1. ↑ Howard Garns – „Number Place“, Dell Pencil Puzzles & Word Games, Ausgabe #16, May p. 6, 1979 New York
2. ↑ Wolfram MathWorld
3. ↑ Les ancêtres français du sudoku (fr. Die französische Ahnengalerie des Sudoku) – Christian Boyer, Mai 2006, PDFormat
4. ↑ YATO Takayuki. Complexity And Completeness Of Finding Another Solution And Its Application To Puzzles.
5. ↑ Jan Finis – „The Mathematics of Puzzle Games“, Lecture Notes in Computer Science, Volume 2696/2003, p. 517-532, 2003 Berlin / Heidelberg

Dieser Artikel wurde in die Liste der Lesenswerten Artikel aufgenommen.