Rechts ein typisches Beispiel für ein Standard-Sudoku mit 25 Ausgangszahlen (die meisten Sudokus haben zwischen 24 und 27 Ausgangszahlen); die oft benutzte Symmetrie ist nicht notwendig und nur ein optisches Merkmal:
Sudoku (japanisch 数独 Sūdoku, "die Zahl, die für sich alleine steht") gehört zur Gattung der Logikrätsel. In der üblichen (Standard)-Version ist es das Ziel, ein 9×9-Gitter mit den Zahlen 1 bis 9 so zu füllen, dass jede Zahl in jeder Einheit (Zeile, Spalte, Box = 3×3-Unterquadrat) genau einmal vorkommt. Ausgangspunkt ist ein Gitter, in dem bereits mehrere Zahlen vorgegeben sind. In Zeitungen und Zeitschriften und auch Online werden heute regelmäßig Sudoku-Rätsel veröffentlicht.
Wie bei allen Rätseln müssen Sudokus eindeutig lösbar sein. Das ist nur aufwändig durch Berechnen aller Möglichkeiten feststellbar.
Die aktuelle Form des Sudoku wurde von Howard Garns erfunden und erstmals im Jahr 1979 in einer Rätselzeitschrift in den Vereinigten Staaten unter dem Namen "Number Place" veröffentlicht. Ab 1984 wurde diese Form zunächst in Japan populär, wo sie auch ihren heutigen Namen "Sudoku" erhielt. Weltweite Verbreitung erhielt das Sudoku-Rätsel erst durch Wayne Gould, nachdem er 2004 ein Programm zur Erstellung von Sudokus entwickelt hatte.
Das Standard-Sudoku mit Einbeziehung der Boxen (neben Zeilen und Spalten) wurde erstmals im Jahr 1979 anonym von dem damals 74-jährigen Architekten und freischaffenden "Rätselonkel" Howard Garns[1] in der Zeitschrift Dell Pencil Puzzles & Word Games als "Number Place" (d.h. Zahlenplatz) veröffentlicht.[2][3]
Die ersten Sudokus wurden in den Vereinigten Staaten publiziert. Seinen Durchbruch erlebte das Zahlenrätsel jedoch zwischen 1984 und 1986, als die japanische Zeitschrift Nikoli es zunächst unter dem Namen "Sūji wa dokushin ni kagiru" regelmäßig abdruckte. Im Jahr 1986 wurde diese sperrige Bezeichnung vom Herausgeber Maki Kaji unter Beibehaltung der jeweils ersten Kanji-Zeichen zu "Sudoku" verkürzt und als Marke registriert.[4] Es werden noch heute in manchen japanischen Zeitschriften diese Rätsel unter "Number Place" - oder seiner Entsprechung in Katakana - abgedruckt.
Der Neuseeländer Wayne Gould lernte Sudoku auf einer Japanreise kennen und entwickelte in sechs Jahren ein Programm, das neue Rätsel per Knopfdruck erzeugen konnte. Die Erzeugung täglicher Sudokus bot er dann der Londoner Tageszeitung "Times" an; diese druckte die ersten Sudoku-Rätsel im November 2004 ab und trug dadurch zu ihrer Verbreitung bei.[5]
Seit Ende 2005 führte der regelmäßige Abdruck in Tageszeitungen und Fernsehzeitschriften zu einer raschen Verbreitung auch in Deutschland, Österreich und der Schweiz. Das Prinzip des Rätsels unterliegt nicht dem Urheberrecht, somit sind keine Gebühren an einen Lizenzgeber zu entrichten. Sudokus können jederzeit frei erstellt und veröffentlicht werden.
Es gibt Sudoku als einfaches Brettspiel, interaktiv im Internet (Online-Sudoku) sowie als Computerspiel. Es gibt sogar Sudokus für Blinde.[6]
Der oft erwähnte Hinweis auf die Lateinischen Quadrate von Leonard Euler als Sudoku-Vorläufer ist falsch: Dort fehlt die wichtige Unterteilung in 3x3-Boxen. Und - was noch wichtiger ist - die Benutzung als Rätsel (mit wenig vorgegebenen Zahlen) ist gar nicht vorhanden.
Die ersten wirklichen Sudoku-Vorläufer erschienen Ende des 19. Jahrhundert in Frankreich. Die Pariser Tageszeitung "Le Siècle" veröffentlichte 1892 ein teilweise gelöstes 9×9-Quadrat mit 3×3-Unterquadraten, aber noch nicht mit den heutigen Sudoku-Regeln. 1895 verfeinerte die Zeitung "La France" das Rätsel zu einem fast modernen Sudoku und nannte es "diabolisches magisches Quadrat". Das 9×9-Quadrat wurde vereinfacht, sodass jede Zeile, Spalte und unterbrochene Diagonale nur noch die Zahlen 1–9 enthielt, die Unterquadrate jedoch nicht mehr markiert waren. Obwohl sie nicht markiert waren, enthielt jedes 3×3-Teilquadrat die Zahlen 1–9, und die zusätzliche Einschränkung bezüglich der unterbrochenen Diagonalen führte zu nur einer Lösung. Diese wöchentlichen Rätsel erschienen etwa ein Jahrzehnt lang in französischen Zeitungen, verschwanden aber um die Zeit des Ersten Weltkriegs. Und das ganz ohne Computer!
Das Standard-Sudoku besteht aus einem quadratischen Gitterfeld mit drei Einheiten: 9 Zeilen, 9 Spalten und 9 Boxen (jede Box in 3×3 Felder unterteilt), insgesamt also 81 Felder. In einige dieser Felder sind schon zu Beginn Zahlen des Bereichs 1 bis 9 eingetragen (Ausgangszahlen oder Vorgaben). Die Aufgabe besteht darin, die leeren Felder des Rätsels so zu füllen, dass in jeder der Zeilen, Spalten und Boxen jede Zahl des Bereiches 1 bis 9 genau einmal vorkommt.
Drei waagrechte oder senkrechte Boxen heißen Blöcke. Bei einem Sudoku können sowohl alle Blöcke als auch die Zeilen bzw. Spalten eines Zeilen- bzw. Spaltenblocks beliebig vertauscht werden; außerdem können auch die Zahlen permutiert werden. Die dabei entstehenden Sudokus sind gleichartig und von gleicher Schwierigkeit.
Während des Lösungsprozesses stehen in jedem Feld oft mehrere den Regeln konforme Zahlen als Kandidaten zur Verfügung, die man notiert und dann schrittweise eliminiert ("Ausdünnen"). Da jede Lösungszahl immer den drei Einheiten zugleich angehört, bewirkt sie in diesen direkte Ausschlüsse. Solche Sperren entstehen zusätzlich durch logische Schlüsse aus besonderen Anordnungen von Kandidaten, z.B. bei zwei gleichen Paaren (2-Tupel).
Obwohl Sudokus meistens mit Zahlen arbeiten, sind zur Lösung keinerlei Rechenkenntnisse erforderlich; man könnte ebenso neun andere abstrakte Symbole wie Buchstaben oder beliebige Zeichen verwenden.
In der grafischen Darstellung werden die nicht besetzten Felder leer gelassen, in der Darstellung als 81-Zeichen-String wird die 0 oder der Punkt benutzt.
Rechts ein typisches Beispiel für ein Standard-Sudoku mit 25 Ausgangszahlen (die meisten Sudokus haben zwischen 24 und 27 Ausgangszahlen); die oft benutzte Symmetrie ist nicht notwendig und nur ein optisches Merkmal:
Im linken Bild ist das Ausgangs-Sudoku dargestellt. Im rechten Bild sieht man den Stand nach 12 Lösungsschritten, bei denen mit den einfachen Methoden "Einzige Position einer Zahl" (grün markiert) und "Einzige Zahl an einer Position" (blau markiert) 12 Zahlen ohne aufwändiges Eintragen von Kandidaten bestimmt werden können.
Man sieht schnell, dass in Zeile 1 die "9" nur in Spalte 9 gesetzt werden kann, da im oberen Block eine "9" schon in den Zeilen 2 und 3 vorkommt ("Einzige Position einer Zahl in einem Block"). Gleiches gilt für die "1" in Zeile 7 und Spalte 6, da dort im mittleren senkrechten Block wegen der "1" in den Spalten 4 und 5 keine andere Stelle frei ist.
Nur etwas schwieriger ist zu sehen, dass in Zeile 4 die "5" nur in Spalte 4 gesetzt werden kann, da in allen anderen Spalten die "5" schon an anderen Stellen gesetzt ist ("Einzige Position einer Zahl in einer Zeile bzw. Spalte").
Mehr Aufwand benötigt man, um die "9" in Zeile 9 und Spalte 5 zu setzen, weil man von dort alle anderen Zahlen sehen kann ("Einzige Zahl an einer Position"). Danach gilt das auch für die "6" links von der gerade gesetzten "9".
Sind alle einfachen Methoden ausgeschöpft, ist es notwendig, dass alle möglichen Kandidaten in allen noch freien Feldern eingetragen werden. Das können manchmal insgesamt 300 oder mehr Kandidaten sein.[15][17][23][24][25]
Danach muss man die Anzahl der Kandidaten schrittweise verkleinern - das sogenannte Ausdünnen. Dazu gibt es weit über 40 bekannte Methoden mit oft vielen Untertypen. Hier werden die ausschlaggebenden Kandidaten rot markiert, die daraufhin streichbaren Kandidaten werden in blau und in eckigen Klammern dargestellt.
Die einfachsten und auch häufigsten Ausdünn-Methoden sind der Zeilen-/Spalten-Test und der Box-Test (meistens über 20 % Anteil).
Zeilen-/Spalten-Test (innerhalb einer Box): Kommt innerhalb einer Zeile bzw. Spalte einer Box ein Kandidat nur in diesen Feldern vor, kann man diesen Kandidaten aus den anderen Feldern dieser Zeile bzw. Spalte außerhalb der betrachteten Box streichen.
Beispiel: Die "8" kommt in der mittleren Box nur in Spalte 5 vor, nicht in Spalte 4 und 6. Also kann die "8" in allen Feldern der Spalte 5 außerhalb dieser Box gestrichen werden.
Box-Test (in einer Zeile oder Spalte): Kommt ein Kandidat innerhalb einer Zeile bzw. Spalte nur genau in einer Box vor, muss diese Zahl also innerhalb dieser Box in der gefundenen Zeile bzw. Spalte stehen. Daher kann der Kandidat aus den anderen Zeilen bzw. Spalten innerhalb dieser Box gestrichen werden.
Beispiel: Die "7" kommt in Zeile 3 nur in der rechten oberen Box vor; d.h. sie muss in dieser Box in der 3. Zeile sein, weshalb in allen anderen Feldern dieser Box die "7" gestrichen werden kann (hier 5 Mal !).
Hier sieht man in Spalte 7 auch schon das 3-Tupel (Tripel) "567" mit möglichen Streichungen in den Zeilen 1 und 2 dieser Spalte (siehe nachfolgende Erklärungen zu N-Tupeln).
Auch sehr häufig sind die direkten oder versteckten N-Tupel. Zu jedem gefundenen N-Tupel gehört ein verstecktes M-Tupel, das aber meistens seltener zu erkennen ist. Die Kandidaten des N-Tupels können dann aus den anderen Feldern gestrichen werden.
2-Tupel oder Doppel: In 2 Feldern einer Einheit kommen genau 2 gleiche Kandidaten vor. Hier kommen die beiden Zahlen "7" und "9" in der 2. Zeile in zwei Feldern alleine vor; damit können beide Zahlen in den anderen Feldern dieser Zeile gestrichen werden. Schwieriger zu erkennen ist hier gleichzeitig das verstecktes Doppel, wobei die beiden Zahlen "4" und "6" nur in 2 Feldern der 2. Zeile neben anderen Kandidaten vorkommen, weshalb die anderen Kandidaten dieser beiden Feldern gestrichen werden können (in diesem Beispiel sind das die gleichen Kandidaten wie beim direkten 2-Tupel).
3-Tupel oder Tripel: In der der mittleren Box des oberen Blocks sieht man 3 Felder, in denen insgesamt nur die Zahlen "5", "7" und "9" vorkommen. Diese Zahlen können damit in den anderen Feldern dieser Box gestrichen werden.
Seltener sind 4-Tupel (Quadrupel), und noch seltener 5-Tupel (Pentupel). 6-Tupel (Sextupel) sind immer verknüpft mit einem versteckten 2-Tupel oder mit einem versteckten 3-Tupel, 7-Tupel (Septupel) mit einem versteckten 2-Tupel.
Entferntes Doppel im Block: Die bei SudokuWiki ziemlich neu beschriebene Methode findet man auch recht häufig. Dabei kommen in 2 verschiedenen Zeilen oder Spalten eines Blocks zwei Felder mit genau 2 gleichen Kandidaten vor. Hier liegen im mittleren senkrechten Block in der 4. und 6. Spalte zwei Felder mit den Kandidaten "59" vor. Da in der 5. Spalte in der nicht betrachteten (unteren) Box nur die "5" vorkommt, kann sie in allen von den beiden Ausgangsfeldern aus gesehen Feldern gestrichen werden, also hier in Spalte 4 der oberen Box und in Spalte 6 der mittleren Box.
Falls in der nicht betrachteten Box (und Zeile bzw. Spalte) keiner der beiden Kandidaten vorkommt, kann man noch mehr streichen, und zwar beide Kandidaten in den Feldern der beiden Ausgangsboxen, die nicht in der Zeile bzw. Spalte mit den "Nicht-Kandidaten" liegen (das wäre hier die Spalte 5).
Die 3. häufigste Gruppe der einfachen Ausdünn-Methoden ist die der Goldenen Ketten oder XY-Ketten.
Hier bilden Felder mit jeweils zwei Kandidaten eine Kette, wenn einer der Kandidaten auch Kandidat des nachfolgenden Kettenglieds ist. Wenn die Zahl des ersten Feldes, die nicht im zweiten Feld vorkommt mit der Zahl des letzten Feldes, die nicht im vorletzten Feld vorkommt, übereinstimmt, dann kann man alle Kandidaten streichen, die sowohl von dem ersten als auch dem letzten Paar aus "gesehen" werden, also in der jeweils gleichen Zeile, Spalte oder Box liegen.
Hier sind das die Felder mit den Kandidaten "57" - "78" - "81" - "14" - "49" - "95", wobei die "5" am Anfang und am Ende vorkommt. Hier können alle vom Anfangsglied und Endglied aus gesehenen Kandidaten "5" gestrichen werden.
Falls sich die beiden Enden sehen, liegt eine Geschlossenen Goldene Kette vor, bei der von jedem Glied der Kette aus Kandidaten gelöscht werden können, was zu sehr vielen Streichungen führen kann.
Eine Goldene Kette der Länge 2 ist identisch mit einem 2-Tupel (Doppel).
XYZ- oder WXYZ-Wing: Eine Erweiterung der Goldenen Kette der Länge 3 ist der XYZ-Wing, bei dem das mittlere Feld 3 Kandidaten besitzt. Man kann diese Methode auch als ein 3-Tupel (Tripel) mit einem Knick auffassen. Eine Verallgemeinerung des XYZ-Wings ist der WXYZ-Wing, bei dem 4 Felder insgesamt 4 verschiedene Kandidaten besitzen. Man kann diese Methode auch als ein 4-Tupel (Quadrupel) mit einem Knick auffassen.
Beim Erweiterten WXYZ-Wing müssen sich 3 der 4 Kandidaten alle gegenseitig sehen, während ein Kandidat in einem Feld, hier die "7", eine der anderen "7" eines der Felder, hier in Zeile 4 und Spalte 8, nicht sieht. Dann können die "7" in allen anderen Feldern, die von den "7" des Erweiterten WXYZ-Wings sichtbar sind, gestrichen werden (Römische Ziffern als Indizes).
Ähnlich häufig findet man Einzelzahl-Ketten bzw. -Gitter, wobei ein Kandidat der verbindende der Kette bzw. des Gitters ist.
Bei einem Einzelzahl-Gitter gibt 2, 3 oder 4 Zeilen und Spalten, in denen dieser Kandidat vorhanden ist, aber entweder in allen diesen Zeilen oder allen diesen Spalten nicht in anderen Feldern vorkommt. Hier sieht man in den drei Zeilen 6, 7 und 9 und in den drei Spalten 2, 5 und 7 das Einzelzahl-Gitter mit der verbindenden Zahl "3". In allen 3 Spalten ist die "3" aber nur in den betrachteten Feldern vorhanden. Daher können alle Kandidaten "3" in den drei Zeilen des Gitters außerhalb der Gitterfelder gestrichen werden, hier 5 Streichungen. Gleichzeitig gibt es auch ein 3*3-Zeilen-Einzelzahl-Gitter in den Zeilen 3, 5 und 8 mit den Spalten 1, 3 und 4.
Eine Einzelzahl-Kette ist ähnlich wie eine Goldene Kette aufgebaut, aber hier mit nur einem verbindenden Kandidaten. Man sieht für eine bestimmte Zahl in den Kandidaten nach, ob in Zeilen oder Spalten oder Boxen diese Zahl genau zwei Mal vorkommt. Hat man mehrere solcher sogenannten starken Verbindungen gefunden, lassen sich diese eventuell so zu einer Einzelzahl-Kette verbinden, dass jeweils ein Anfang oder Ende in der gleichen Zeile, Spalte oder Box wie eine andere starke Verbindung liegen. Wenn sowohl vom Anfang als auch vom Ende dieser Kette ein oder mehrere Felder "gesehen" werden, kann die bestimmte Zahl aus diesen Feldern gestrichen werden. In wenigen Fällen findet man auch eine Geschlossene Einzelzahl-Kette mit mehr Streichungen.
Eine Sonderform ist dabei die Einzelzahl-Widerspruchs-Kette. Hier sieht man ebenfalls für eine bestimmte Zahl in den Kandidaten nach, ob in Zeilen oder Spalten oder Boxen diese Zahl genau zwei Mal oder auch mehr als zwei Mal vorkommt. Hat man mehrere solcher Fälle gefunden, lassen sich diese eventuell zu einer Kette verbinden. Nach einer schwachen Verbindung muss aber direkt eine starke Verbindung folgen. Dann nimmt man an, dass im ersten Glied und den anderen ungeraden Stellen der Kette die Zahl gesetzt ist, in den anderen aber nicht. Das führt dann oft zu Widersprüchen, etwa dass in einer Zeile, Spalte oder Box keine solche Zahl mehr auftreten kann oder diese Zahl mehr als einmal auftritt, weshalb daher die Zahl in allen ungeraden Kettengliedern ab der ersten bis vor der ersten schwachen Verbindung gestrichen werden kann.
Hier nimmt man an, dass die "1" in Zeile 4 und Spalte 5 gesetzt ist. Dann kann sie nicht in Zeile 4 und Spalte 1 gesetzt sein, muss also in Zeile 5 und Spalte 1 sein (Römische Ziffern als Indizes). Das ist aber ein Widerspruch, denn damit ist überall in Spalte 6 keine "1" möglich. Also kann die anfangs angenommene "1" gestrichen werden. Manchmal ist eine Einzelzahl-Widerspruchs-Kette auch gleichzeitig eine Einzelzahl-Kette, wobei noch mehr Kandidaten gestrichen werden können.
Wichtige Ausdünn-Methoden sind noch die Ausschluss-Rechtecke und Ausschluss-Ketten.
Ausschluss-Rechtecke: Hier betrachtet man 4 Felder, die in 2 Zeilen, 2 Spalten und in 2 Boxen liegen und dort neben anderen immer die zwei gleichen Hauptkandidaten haben. Da ein Sudoku eindeutig lösbar sein muss, kann man dann bestimmte andere Kandidaten streichen. Bei dieser Methode gibt es etwa 20 Typen, von denen hier die 3 wichtigsten dargestellt werden.
Ausschluss-Rechteck Typ 1: Hier liegen in Zeile 1 und Zeile 8, Spalte 4 und Spalte 5, Box oben Mitte und Box unten Mitte 4 Felder, in denen "35" vorkommt, aber in der ersten dieser Felder auch noch die Kandidaten "4", "7" und "9". Wäre im ersten Feld eine "3" oder eine "5", ist das Sudoku mehrdeutig. Also können dort die "3" und die "5" gestrichen werden.
Ausschluss-Rechteck Typ 4A: Dabei haben zwei der Ausschluss-Rechteck-Felder zusätzliche Kandidaten, hier in Zeile 1 und Zeile 4, Spalte 7 und Spalte 9, rechte obere Box und rechte mittlere Box (Römische Ziffern als Indizes). Zwei Felder haben nur die Hauptkandidaten "19", die Felder in Spalte 7 haben aber noch "4", "7" und "8". In Zeile 4 ist aber die "9" nur in den beiden Ausschluss-Rechteck-Feldern vorhanden. Daher muss der andere Kandidat "1" im Feld in Zeile 1 mit den Zusatzkandidaten gestrichen werden.
Ausschluss-Rechteck Typ 7B: Hier haben drei der Ausschluss-Rechteck-Felder zusätzliche Kandidaten, hier in Zeile 1 und Zeile 2, Spalte 2 und Spalte 8, linke obere Box und rechte obere Box (Großbuchstaben als Indizes). Wenn einer der beiden Hauptkandidaten, hier die "2", nur in den vier Feldern des Ausschluss-Rechtecks vorkommt, kann der andere Hauptkandidat, hier "1", im Feld, die dem Ausschluss-Rechteck-Feld mit nur den zwei Hauptkandidaten gegenüber liegt, gestrichen werden.
Quasi-Ausschluss-Rechtecke: Dies sind unvollständige Ausschluss-Rechtecke, z.B. wenn schon einige Felder eindeutig besetzt wurden, die aber temporär wieder eingesetzt werden, um ein Ausschluss-Verfahren zu ermöglichen.
Weitergehend gibt es auch Ausschluss-Ketten (und Quasi-Ausschluss-Ketten). Dabei betrachtet man 2*N Felder, die in N Zeilen, N Spalten und in N Boxen liegen und dort neben anderen immer die zwei gleichen Hauptkandidaten haben. Bis zu 10er-Ausschluss-Ketten (N = 5) wurden schon beobachtet.
Wenn man mit den oben erwähnten relativ einfachen Ausdünn-Methoden nicht weiter kommt, helfen eventuell auch allgemeine Widerspruchs-Ketten (man nimmt an, dass ein Kandidat gesetzt ist oder nicht gesetzt ist, und versucht dann durch Schlussfolgerungen, einen Widerspruch zu erzeugen) oder Alternativ-Ketten, bei denen man von einem Feld aus mit einem der Kandidaten über zwei Wege zu einem Zielfeld kommt, dort aber unterschiedliche Ergebnisse erzeugt oder von beiden Kandidaten im Anfangsfeld zu genau einem Kandidaten im Zielfeld kommt.[15]. Bei sehr schwierigen Sudokus wird man noch kompliziertere Ausdünn-Methoden von Exocet bis hin zu Bowman's Bingo anwenden müssen.[17]
Die Vermutung, dass 17 die minimale Anzahl an vorbesetzten Feldern ist, für die ein eindeutig lösbares Rätsel existiert,[3][7] bewies ein Forschungsteam um Gary McGuire (University College Dublin) mit Hilfe von Computern (von Januar bis Dezember 2011). Die von ihnen programmierte erschöpfende Suche benötigte sieben Millionen Stunden Rechenzeit parallel auf Hunderten von Prozessoren.[8][9] Ganz auf Computer-Rechnungen basierte Beweise werden inzwischen anerkannt. Ein mathematischer Beweis - ohne Verwendung eines Computers, der möglicherweise darüber Aufschluss geben könnte, warum die Grenze bei 17 und nicht z. B. bei 16 liegt, steht noch aus.
Bis 2009 hat Gordon Royle, Professor an der University of Western Australia, alle bekannten Sudokus mit 17 Ausgangszahlen zusammengestellt, wobei die Sudokus in eine normierte Darstellung umgeformt wurden, um gleichartige auszuschließen. Außer diesen 49151 Sudokus wurden bis 2019 nur noch 7 weitere Sudokus gefunden,[7][10] wobei der Aufwand, weitere Sudokus mit 17 Ausgangszahlen zu finden, enorm ist. Für die normierte Darstellung wird ein Sudoku als 81-Zeichen-String mit 0 als Platzhalter definiert und solange durch Block-Vertauschungen, Zeilen- bzw. Spaltenvertauschungen und Permutationen der Zahlen 1 bis 9 umgeformt, bis der String als kleinste Zahl interpretiert werden kann.
Bertram Felgenhauer und Frazer Jarvis konnten 2005 zeigen, dass es 6.670.903.752.021.072.936.960 (ca. 6,67 Trilliarden oder 6,67⋅1021) verschiedene Sudoku-Lösungen (also vollständig ausgefüllte Sudokus) gibt.[26]
Zählt man nur die vollständig ausgefüllten Sudokus ohne Vertauschung der Ziffern (also z. B. nur die mit der geordneten Zahlenreihe in der ersten Zeile), so ergeben sich 18.383.222.420.692.992 (ca. 18,4 Billiarden) Sudoku-Lösungen. Zählt man nur die Sudokus, die zusätzlich auch unter Drehungen oder Spiegelungen verschieden sind, so verbleiben nur noch 5.472.730.538 (5,5 Milliarden) verschiedene Sudoku-Lösungen (Ed Russell und Frazer Jarvis 2006).[29]
Ingolf Giese berechnete daraus mit statistischen Methoden die Anzahl aller möglichen Sudoku-Rätsel und kommt dabei auf etwa 1,3⋅1034.[30]
Es gibt sehr wenig Literatur über das Problem der Bewertung eines Sudokus. Aber einige Autoren beschreiben das Problem sehr ausführlich.[12][16][11][14][15]
Alle diese Autoren betonen, dass die Anzahl der vorgegebenen Zahlen kein Kriterium für die Schwierigkeit eines Sudokus ist. Es ist zwar oft so, dass ein Sudoku mit vielen Ausgangszahlen einfacher zu lösen ist als eines mit wenigen Ausgangszahlen, aber prinzipiell ist die Aussage "Je weniger Felder in einem Sudoku-Rätsel vorbesetzt sind, desto schwieriger ist es in der Regel zu lösen" absolut falsch. Leider werden die meisten Sudokus, die man in Zeitungen, Zeitschriften und Büchern und auch in Online-Sudoku-Webseiten findet, nach dieser falschen Regel eingeordnet (außer bei speziellen Sudoku-Heften z.B. von Stefan Heine oder Eberhard Krüger) - wahrscheinlich auch, weil es recht aufwändig (und nicht objektiv definierbar und allgemein anerkannt) ist, einen Schwierigkeitsgrad zu bestimmen.[31][32] Wichtiger als die Anzahl ist die Verteilung der Ausgangszahlen, wie das folgende Beispiel (als eines von vielen Tausenden) zeigt:
Beide Sudokus unterscheiden sich nur in einer Zahl: Die "3" (grün) in Zeile 5 und Spalte 2 im linken Sudoku wurde ersetzt durch die "4" (rot) in Zeile 6 und Spalte 6 im rechten Bild. Beide fast identische Sudokus haben also die gleiche Anzahl von Ausgangszahlen, jedoch ist das linke Sudoku mit nur 9 Punkten (Bewertung nach [15]) super einfach bei 56 immer sehr einfachen Schritten (mit nur 2 Mal "Einzig mögliche Zahl"), das rechte Sudoku ist aber mit 1326 Punkten extrem schwierig und erfordert 66 Ausdünnschritte, darunter 4 Goldene Ketten, 14 Einzelzahl-Widerspruchs-Ketten, 32 Widerspruchs-Ketten und 7 Mal Bowman's Bingo.
Von den weltweit bisher 49158 (von Gordon Royle und anderen gefundenen[7]) unterschiedlichen Sudokus mit 17 Ausgangszahlen (die oft als "besonders schwierig" klassifiziert werden) sind etwa 82 % "einfach" lösbar! Und es gibt Sudokus mit mehr als 50 und sogar 64 Ausgangszahlen, die "schwierig" zu lösen sind. Einfach und schwierig bezieht sich dabei auf die Einfachheit bzw. Komplexität der benötigten Methoden, um das Sudoku zu lösen.[11]
Die genannten Autoren befassen sich daher mit Methoden, eine Bewertung zu erstellen. Dabei wird in allen Fällen eine Punktzahl für die jeweils benutzte Methode gegeben, die zum Einsetzen einer Zahl oder dem Ausstreichen eines Kandidaten benötigt wird. Natürlich ist diese Punktzahl nicht absolut festlegbar, sondern Ansichtssache und Erfahrung des jeweiligen Autors. Von den über 40 bekannten Lösungsmethoden sind einige einfach zu benutzen, andere nur für geübte Sudoku-Löser benutzbar.
Bei Jan Feldmann (Sudoku-Coach) [12] wird zusätzlich auf zwei Arten der Gesamtbewertung hingewiesen: Entsprechend der Idee von Nicolas Juillerat's "Sudoku Explainer" [13] wird nur das Maximum benutzt, egal, wie oft die schwierigste Methode eingesetzt werden musste. Nach Bernhard Hobiger [14] wird die Summe aller Punktzahlen aller benutzten Methoden zur Festlegung der Schwierigkeit benutzt (wobei man die jeweiligen Punktzahlen selbst festlegen kann). Bei Ingolf Giese [15] werden sogar drei Methoden benutzt: Die Maximalzahl, die Gesamtsumme und eine gemittelte Gesamtsumme (2-Norm oder Euklidische Norm, also die Wurzel aller Punkte zum Quadrat).
Andrew Stuart [16] schreibt: Der Schwierigkeitsgrad lässt sich allein durch die Zählung der Lösungsmöglichkeiten in allen Phasen des Spiels ermitteln. Engpässe entstehen, wenn es nur wenige oder nur eine Chance für eine korrekte Schlussfolgerung gibt, und diese machen das Rätsel schwieriger. In seinem Solver [17] findet man die Funktion "Grader", bei der die Gesamtpunktzahl angegeben wird, aber welche Methode welche Punktzahl hat, fehlt hier. Die Reihenfolge der etwa 40 möglichen Lösungsmethoden zeigt aber einen steigenden Schwierigkeitsgrad an.
Das Farb-Sudoku ist die einzige konforme Erweiterung mit 4 statt 3 Einheiten: Jedes Feld innerhalb einer Box wird durch 9 verschieden farbige Farbbereiche dargestellt. Analog den Zeilen und Spalten, wobei die erste Zeile die Anfangspunkte der Spalten und die erste Spalte die Anfangspunkte der Zeilen sind, gilt für die Boxen und Farbbereiche, dass die erste Box die Anfangspunkte der Farbbereiche und die ersten Farbbereiche die Anfangspunkte der Boxen sind.
Ausschluss-Rechtecke sind nur möglich, wenn sie auch in nur 2 Farbbereichen vorkommen.
Es wurden schon Farb-Sudokus mit nur 11 Ausgangszahlen gefunden. Da für Farb-Sudokus aber ein Farbdruck notwendig ist, sind sie selten zu finden.[18][27]
Bei [18] werden auch weitere Ausdünn-Methoden wie z.B. die Farbbereich-Tests erklärt.
Am häufigsten sind hier die Test-Methoden, wobei die Zeilen-/Spalten- und Box-Tests erweitert sind um Farb-Tests (knapp 50 %), gefolgt von den N-Tupeln und Entfernten Doppeln im Block und danach von den Einzelzahl-Widerspruchs-Ketten. Ausschluss-Rechtecke und Quasi-Ausschluss-Rechtecke sind aber seltener.
Die andere einfache Erweiterung benutzt die beiden (Haupt-)Diagonalen, bei der zusätzlich alle Felder jeder Diagonale mit den Zahlen von 1 bis 9 besetzt werden müssen. Es wurden schon Diagonal-Sudokus mit nur 12 Ausgangszahlen gefunden. Diese Erweiterung ist recht häufig zu finden.[28]
Diagonal-Sudokus sind die am häufigsten verbreitete Sudoku-Erweiterung, wohl auch die häufigste Sudoku-Variante überhaupt.
Bei Diagonal-Sudokus findet man sehr viele Einzelzahl-Widerspruchs-Ketten (insbesondere durch Widersprüche in einer Diagonalen) - fast 24 %, doppelt so oft wie bei Farb-Sudokus.
Bei [19] werden auch weitere Ausdünn-Methoden wie z.B. die Diagonal-Zange und die Diagonalen-Tests erklärt.
Am häufigsten sind hier die Test-Methoden, wobei die Zeilen-/Spalten- und Box-Tests erweitert sind um Diagonal-Tests (etwa 40 %), gefolgt von den Einzelzahl-Widerspruchs-Ketten und danach von den N-Tupeln und Entfernten Doppeln im Block, den Goldenen Ketten und den speziellen Diagonal-Zangen. Ausschluss-Rechtecke und Quasi-Ausschluss-Rechtecke sind aber recht selten.
Die Kombination beider Erweiterungen, also "Farbbereich" und "(Haupt-)Diagonale", ist kaum zu finden, aber auch wegen dem dafür notwendigen Farbdruck.
Bei [20] finden sich viele Erläuterungen und Beispiele. Erwähnt werden Fardiagonal-Sudokus aber auch bei [21] und [22].
Am häufigsten sind hier die Test-Methoden, wobei die Zeilen-/Spalten- und Box-Tests erweitert sind um Farb- und Diagonalen-Tests (über 50 %), gefolgt von den Einzelzahl-Widerspruchs-Ketten und danach von den N-Tupeln und Entfernten Doppeln im Block. Ausschluss-Rechtecke sind extrem selten.
Alle anderen Varianten (inklusive der Größenänderung von 6x6- bis zu 25x25-Sudokus) verlassen die Standard-Sudoku-Form und -regeln.
Diese sollten besser auf einer getrennten Webseite dargestellt werden, was auch für die Sudoku-Wettbewerbe gilt.
Ganz weggelassen werden sollten die Punkte: Kandidaten-Notation, Erstellung neuer Sudokus, Algorithmisch, Die Mathematik hinter Sudoku, da sie wenig sinnvoll sind.