Sudoku

A typical Sudoku puzzle

The solution to the puzzle above

Sudoku (/suːˈdoʊkuː,-ˈdɒk-,sə-/; Japanese: 数独, romanized: sūdoku, lit.'digit-single'; originally called Number Place)^[1] is a logic-based,^[2][3]combinatorial^[4] number-placement puzzle. In classic Sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which, for a well-posed puzzle, has a single solution.

French newspapers featured similar puzzles in the 19th century, and the modern form of the puzzle first appeared in 1979 puzzle books by Dell Magazines under the name Number Place.^[5] However, the puzzle type only began to gain widespread popularity in 1986 when it was published by the Japanese puzzle company Nikoli under the name Sudoku, meaning "single number".^[6] In newspapers outside of Japan, it first appeared in The Conway Daily Sun (New Hampshire) in September 2004, and then The Times (London) in November 2004, both of which were thanks to the efforts of the Hong Kong judge Wayne Gould, who devised a computer program to rapidly produce unique puzzles.^[7]

Zahlenrätsel tauchten Ende des 19. Jahrhunderts in Zeitungen auf, als französische Rätselautoren begannen, mit dem Entfernen von Zahlen aus magischen Quadraten zu experimentieren . Die Pariser Tageszeitung Le Siècle veröffentlichte am 19. November 1892 ein teilweise gelöstes 9×9-Quadrat mit 3×3-Unterquadraten. ^{[ 8 ]} Es handelte sich nicht um ein Sudoku, da es zweistellige Zahlen enthielt und zur Lösung Arithmetik statt Logik erforderte, aber es wies wichtige Gemeinsamkeiten auf: Die Summe jeder Zeile, Spalte und jedes Unterquadrats war gleich.

Am 6. Juli 1895 verfeinerte Le Siècles Konkurrenzzeitschrift La France das Rätsel zu einem fast modernen Sudoku und nannte es „carré magique diabolique “ („diabolisches magisches Quadrat“). Sie vereinfachte das 9×9-Magische-Quadrat-Rätsel, indem sie festlegte, dass jede Zeile, Spalte und unterbrochene Diagonale nur die Zahlen 1–9 enthielt, die Teilquadrate jedoch nicht markierte. Obwohl sie nicht markiert waren, enthielt jedes 3×3-Teilquadrat tatsächlich die Zahlen 1–9, und die zusätzliche Einschränkung bezüglich der unterbrochenen Diagonalen führte zu nur einer Lösung. ^{[ 9 ]}

Diese wöchentlichen Rätsel waren etwa ein Jahrzehnt lang ein fester Bestandteil französischer Zeitungen wie L'Écho de Paris , verschwanden aber etwa zur Zeit des Ersten Weltkriegs . ^{[ 10 ]}

Das moderne Sudoku wurde höchstwahrscheinlich anonym von Howard Garns , einem 74-jährigen pensionierten Architekten und freiberuflichen Rätselkonstrukteur aus Connersville, Indiana , entworfen und 1979 von Dell Magazines unter dem Titel „Number Place“ (die frühesten bekannten Beispiele des modernen Sudoku) veröffentlicht. ^{[ 1 ]} Garns’ Name stand stets auf der Liste der Mitwirkenden in Ausgaben von „Dell Pencil Puzzles and Word Games“ , die „Number Place“ enthielten, fehlte jedoch in Ausgaben ohne „Number Place“. ^{[ 11 ]} Er starb 1989, bevor er die weltweite Verbreitung seiner Erfindung miterleben konnte. ^{[ 11 ]} Ob Garns die oben genannten französischen Zeitungen kannte, ist unklar.

Das Puzzle wurde in Japan von Maki Kaji (鍜治 真起, Kaji Maki ) , Präsident der Nikoli- Puzzle-Firma, in der Zeitung Monthly Nikolist im April 1984 ^{[ 11 ]} als Sūji wa dokushin ni kagiru (数字は独身に限る) eingeführt , was mit „die Ziffern müssen einzeln sein“ übersetzt werden kann. oder als „die Ziffern sind auf ein Vorkommen beschränkt“ (auf Japanisch bedeutet „ dokushin “ eine „unverheiratete Person“). Der Name wurde später zu Sudoku (数独) abgekürzt, wobei nur das erste Kanji zusammengesetzter Wörter verwendet wurde, um eine kürzere Version zu bilden. ^{[ 11 ]} „Sudoku“ ist in Japan eine eingetragene Marke ^{[ 12 ]} und das Rätsel wird allgemein als „Number Place “ (ナンバープレース, Nanbāpurēsu ) oder, informeller, als Kurzform der beiden Wörter „Num(ber) Pla(ce)“ (ナンプレ, Nanpure ) bezeichnet. 1986 führte Nikoli zwei Neuerungen ein: Die Anzahl der vorgegebenen Zahlen wurde auf maximal 32 begrenzt, und die Rätsel wurden „symmetrisch“ (d. h. die vorgegebenen Zahlen wurden in rotationssymmetrischen Feldern verteilt ). Es erscheint heute in etablierten japanischen Zeitschriften wie der Asahi Shimbun .

1997 entdeckte der Hongkonger Richter Wayne Gould in einer japanischen Buchhandlung ein unvollendetes Puzzle. Innerhalb von sechs Jahren entwickelte er ein Computerprogramm, um schnell einzigartige Puzzles zu generieren. ^{[ 5 ]}

Die erste Zeitung außerhalb Japans, die ein Sudoku-Rätsel veröffentlichte, war die Conway Daily Sun (New Hampshire), die im September 2004 ein Rätsel von Gould veröffentlichte. ^{[ 13 ] [ 14 ]}

Gould unterbreitete Zeitungen die Idee, Sudoku-Rätsel zu veröffentlichen, und bot die Rätsel kostenlos an, im Gegenzug dafür, dass die Zeitungen ihn als Urheber nannten und auf seine Website mit Lösungen und weiteren Rätseln verlinkten. ^{[ 15 ]}

Da er wusste, dass britische Zeitungen eine lange Tradition im Veröffentlichen von Kreuzworträtseln und anderen Rätseln haben, empfahl er Sudoku der britischen Zeitung „The Times“ , die es am 12. November 2004 (unter dem Namen „Su Doku“) veröffentlichte. Der erste Leserbrief an „The Times“ zu Sudoku erschien am folgenden Tag, dem 13. November. Er stammte von Ian Payn aus Brentford , der sich darüber beschwerte, dass er durch das Rätsel seine U-Bahn -Haltestelle verpasst hatte . ^{[ 16 ]} Sudoku-Rätsel verbreiteten sich rasch und wurden zu einer festen Rubrik in anderen Zeitungen. ^{[ 5 ] [ 17 ]}

Der rasante Aufstieg von Sudoku in Großbritannien – von einem relativ unbekannten Rätsel bis hin zur Titelseite nationaler Zeitungen – rief Kommentare und Parodien in den Medien hervor (beispielsweise als die G2- Beilage des Guardian damit warb, als erste Zeitungsbeilage auf jeder Seite ein Sudoku-Gitter zu präsentieren). ^{[ 18 ]} Die Times erkannte die unterschiedliche psychologische Wirkung einfacher und schwieriger Rätsel und führte am 20. Juni 2005 beide Varianten nebeneinander ein. Ab Juli 2005 bot Channel 4 täglich ein Sudoku-Spiel in seinem Videotext- Angebot an. Am 2. August präsentierte die BBC-Programmzeitschrift Radio Times ein wöchentliches Super-Sudoku mit einem 16×16-Gitter.

Die weltweit erste Live-Sudoku-Show im Fernsehen, „Sudoku Live“ , war ein Rätselwettbewerb, der erstmals am 1. Juli 2005 auf dem britischen Pay-TV-Sender Sky One ausgestrahlt wurde . Moderiert wurde die Sendung von Carol Vorderman . Neun Teams mit je neun Spielern (darunter ein Prominenter), die verschiedene geografische Regionen repräsentierten, traten gegeneinander an, um ein Sudoku zu lösen. Jeder Spieler benutzte ein Handgerät, um die Zahlen für die vier Felder einzugeben. Phil Kollin aus Winchelsea, England , gewann den Hauptpreis der Staffel und nahm über 23.000 Pfund mit nach Hause. Die Zuschauer zu Hause nahmen an einem separaten interaktiven Wettbewerb teil, den Hannah Withey aus Cheshire für sich entschied . ^{[ 19 ]}

Später im Jahr 2005 startete die BBC die Spielshow SUDO-Q , die Sudoku mit Allgemeinwissen verband. Dabei wurden jedoch nur 4×4- und 6×6-Rätsel verwendet. Die Show wurde 2007 nach vier Staffeln eingestellt.

Seit 2006 wird jährlich eine Weltmeisterschaft im Sudoku vom Welträtselverband (World Puzzle Federation) veranstaltet , außer in den Jahren 2020 und 2021 während der COVID-19-Pandemie .

Im Jahr 2006 veröffentlichte eine Sudoku-Website ein Tributlied des australischen Songwriters Peter Levy. Der Download wurde jedoch aufgrund des hohen Besucheraufkommens später wieder entfernt. Die japanische Botschaft nominierte das Lied für einen Preis, und Levy gab an, mit Sony in Japan über eine Veröffentlichung als Single zu verhandeln. ^{[ 20 ]}

Der internationale Sudoku-Wettbewerb erreichte Mitte der 2020er Jahre einen neuen Höhepunkt. Bei der 18. Sudoku-Weltmeisterschaft , die im Oktober 2025 in Ungarn stattfand, sicherte sich der Chinese Tantan Dai den Einzelweltmeistertitel. ^{[ 21 ]} Darauf folgte die 7. Asiatische Sudoku-Meisterschaft im Februar 2026 in Bangkok , bei der Hu Yuxuan die chinesische Nationalmannschaft zu einem Triumph in allen Meisterklassen führte und damit die Wettbewerbsdominanz der Region weiter festigte. ^{[ 22 ]}

Sudoku-Software ist auf PCs, Websites und Mobiltelefonen sehr beliebt. Sie ist in vielen Linux- Distributionen vorinstalliert. Die Software wurde auch für Videospielkonsolen wie Nintendo DS , PlayStation Portable , Game Boy Advance , Xbox Live Arcade , den E-Book-Reader Nook , das Kindle Fire Tablet, verschiedene iPod- Modelle und das iPhone veröffentlicht . Auch viele Nokia -Handys boten Sudoku an. Tatsächlich waren nur zwei Wochen nach dem Start des Online -App-Stores im iTunes Store von Apple Inc. am 11. Juli 2008 bereits fast 30 verschiedene Sudoku-Spiele verfügbar, die von verschiedenen Softwareentwicklern speziell für iPhone und iPod Touch entwickelt worden waren. Sudoku-Spiele wurden auch schnell für Webbrowser- Nutzer und praktisch alle Spiele-, Handy- und Computerplattformen zugänglich .

Bis 2026 wird der digitale Vertrieb des Spiels weitgehend auf browsernative HTML5- Umgebungen umgestellt, um plattformübergreifende Zugänglichkeit zu gewährleisten. Dieser Wandel wurde 2025 deutlich, als Sakana AI Sudoku als primären Benchmark für „System 2“-Schlussfolgerungen in großen Sprachmodellen nutzte . ^{[ 23 ]} In Zusammenarbeit mit der Cracking the Cryptic Community etablierte das Labor eine Testumgebung für logisches Denken, in der die KI-Logik anhand ihrer Fähigkeit gemessen wird, komplexe deduktive Ketten ohne menschliche Unterstützung auszuführen. ^{[ 24 ] [ 25 ]} Moderne Implementierungen auf stark frequentierten Plattformen wie der New York Times , dem Internet Archive und webbasierten Portalen wie CrazyGames demonstrieren den Übergang des Genres zu modernen Webstandards, die die ursprüngliche deduktive Logik des Spiels sowohl auf mobilen als auch auf Desktop-Oberflächen beibehalten. ^{[ 26 ] [ 27 ]}

Im Juni 2008 wurde ein australischer Drogenprozess mit Geschworenen, der über 1 Million australische Dollar kostete , abgebrochen, als entdeckt wurde, dass vier oder fünf der zwölf Geschworenen Sudoku spielten, anstatt den Beweismitteln zuzuhören. ^{[ 28 ]}

Ein Nonomino oder Puzzle- Sudoku, wie es im Sunday Telegraph zu sehen war ...

...und ihre Lösung (rote Zahlen)

Obwohl das 9×9-Gitter mit 3×3-Feldern mit Abstand am häufigsten vorkommt, existieren viele weitere Varianten. Beispiele hierfür sind 4×4-Gitter mit 2×2-Feldern; 5×5-Gitter mit Pentomino -Feldern wurden unter dem Namen Logi-5 veröffentlicht; bei der Weltmeisterschaft im Sudoku gab es ein 6×6-Gitter mit 2×3-Feldern und ein 7×7-Gitter mit sechs Heptomino- Feldern und einem disjunkten Feld. Auch größere Gitter oder verschiedene unregelmäßige Formen sind möglich (unter verschiedenen Namen wie Suguru , Tectonic , Jigsaw Sudoku usw.). Die Times bietet ein 12×12-Gitter namens „Dodeka Sudoku“ mit 12 Feldern à 4×3 Quadraten an. Dell Magazines veröffentlicht regelmäßig 16×16-Rätsel namens „Number Place Challenger“ (mit den Zahlen 1–16 oder den Buchstaben AP). Nikoli bietet gigantische 25×25-Rätsel namens „Sudoku the Giant“ an. Ein 100×100-Gitterrätsel mit dem Namen Sudoku-zilla wurde im Jahr 2010 veröffentlicht. ^{[ 29 ]}

Under the name "Mini Sudoku", a 6×6 variant with 3×2 regions appears in the American newspaper USA Today and elsewhere. The object is the same as that of standard Sudoku, but the puzzle only uses the numbers 1 through 6. A similar form, for younger solvers of puzzles, called "The Junior Sudoku", has appeared in some newspapers, such as some editions of The Daily Mail.

Another common variant is to add limits on the placement of numbers beyond the usual row, column, and box requirements. Often, the limit takes the form of an extra "dimension"; the most common is to require the numbers in the main diagonals of the grid to also be unique. The aforementioned "Number Place Challenger" puzzles are all of this variant, as are the Sudoku X puzzles in The Daily Mail, which use 6×6 grids.

A Killer Sudoku puzzle

And its solution

The killer sudoku variant combines elements of sudoku and kakuro. A killer sudoku puzzle is made up of 'cages', typically depicted by boxes outlined with dashes or colours. The sum of the numbers in a cage is written in the top left corner of the cage, and numbers cannot be repeated in a cage.

Puzzles constructed from more than two grids are also common. Five 9×9 grids that overlap at the corner regions in the shape of a quincunx is known in Japan as Gattai 5 (five merged) Sudoku. In The Times, The Age, and The Sydney Morning Herald, this form of puzzle is known as Samurai Sudoku. The Baltimore Sun and the Toronto Star publish a puzzle of this variant (titled High Five) in their Sunday edition. Often, no givens are placed in the overlapping regions. Sequential grids, as opposed to overlapping, are also published, with values in specific locations in grids needing to be transferred to others.

A tabletop version of Sudoku can be played with a standard 81-card Set deck (see Set game). A three-dimensional Sudoku puzzle was published in The Daily Telegraph in May 2005. The Times also publishes a three-dimensional version under the name Tredoku. Also, a Sudoku version of the Rubik's Cube is named Sudoku Cube.

Es wurden zahlreiche weitere Varianten entwickelt. ^{[ 30 ] [ 31 ] [ 32 ]} Einige bestehen aus unterschiedlichen Formen in der Anordnung überlappender 9×9-Gitter, wie beispielsweise Schmetterling, Windmühle oder Blume. ^{[ 33 ]} Andere variieren die Lösungslogik. Eine davon ist das „Größer-als-Sudoku“. Hierbei wird ein 3×3-Sudoku-Gitter mit 12 Symbolen für „Größer als“ (>) oder „Kleiner als“ (<) auf der gemeinsamen Zeile zweier benachbarter Zahlen verwendet. ^{[ 11 ]} Eine weitere Variante ist das „Hinweislose Sudoku“. Hierbei werden neun 9×9-Sudoku-Gitter jeweils in einem 3×3-Raster angeordnet. Das mittlere Feld jedes 3×3-Gitters aller neun Rätsel bleibt leer und bildet so ein zehntes Sudoku-Rätsel ohne ausgefüllte Felder; daher der Name „hinweislos“. ^{[ 33 ]} Beispiele und weitere Varianten finden sich im Sudoku-Glossar .

Dieser Abschnitt bezieht sich auf das klassische Sudoku und lässt Jigsaw-, Hyper- und andere Varianten außer Acht. Ein ausgefülltes Sudoku-Gitter ist eine spezielle Art von lateinischem Quadrat mit der zusätzlichen Eigenschaft, dass in keinem der neun Blöcke (oder 3×3- Felder ) Werte doppelt vorkommen. ^{[ 34 ]}

Das allgemeine Problem, Sudoku-Rätsel auf n² ^× n² ^- Gittern mit n × n Blöcken zu lösen , ist bekanntermaßen NP-vollständig . ^{[ 35 ]} Viele Sudoku-Lösungsalgorithmen , wie z. B. Brute-Force -Backtracking und Dancing Links, können die meisten 9 × 9-Rätsel effizient lösen. Mit zunehmendem n tritt jedoch eine kombinatorische Explosion auf, die die Eigenschaften der Sudokus, die mit steigendem n konstruiert, analysiert und gelöst werden können, praktisch begrenzt . Ein Sudoku-Rätsel lässt sich als Graphfärbungsproblem formulieren . ^{[ 36 ]} Ziel ist es, eine 9-Färbung eines gegebenen Graphen zu konstruieren, wenn eine partielle 9-Färbung vorliegt.

Die Mindestanzahl an Hinweisen für ein korrektes Sudoku beträgt 17. ^{[ 37 ]} Zehntausende verschiedene Sudoku-Rätsel enthalten nur 17 Hinweise. ^{[ 38 ]}

Die Anzahl der klassischen 9×9-Sudoku-Lösungsgitter beträgt 6.670.903.752.021.072.936.960 oder ungefähr6,67 × 10²¹ . ^{[ 39 ] Die Anzahl der} im Wesentlichen unterschiedlichen Lösungen ist viel kleiner, wenn Symmetrien wie Drehung, Spiegelung, Permutation und Umbenennung berücksichtigt werden: 5.472.730.538. ^{[ 40 ]}

Im Gegensatz zur Anzahl vollständiger Sudoku-Gitter ist die Anzahl minimaler 9×9-Sudoku-Rätsel nicht genau bekannt. (Ein minimales Rätsel ist ein Rätsel, bei dem kein Hinweis entfernt werden kann, ohne die Eindeutigkeit der Lösung zu verlieren.) Statistische Verfahren in Kombination mit einem Rätselgenerator zeigen jedoch, dass etwa (mit einem relativen Fehler von 0,065 %) 3,10 × 10³⁷ ^minimale Rätsel und 2,55 × 10²⁵ ^nicht wesentlich äquivalente minimale Rätsel existieren. ^{[ 41 ]}

• Delahaye, Jean-Paul (Jun 2006). "The Science Behind Sudoku"(PDF). Scientific American. 294 (6): 80–87. Bibcode:2006SciAm.294f..80D. doi:10.1038/scientificamerican0606-80. JSTOR 26061494. PMID 16711364.
• Provan, J. Scott (Oct 2009). "Sudoku: Strategy Versus Structure". American Mathematical Monthly. 116 (8): 702–707. doi:10.4169/193009709X460822. S2CID 38433481. Also as UNC/STOR/08/04Archived 2010-06-13 at the Wayback Machine.

• 'Father of Sudoku' puzzles next move (BBC)