Sudoku

Sudoku-Beispiel

Sudoku gelöst

Sudoku ( japanisch : 数独, sūdoku ) ist ein mathematisches Spiel , das in den späten 1970er Jahren erfunden wurde, in den 1980er Jahren in Japan an Popularität gewann und 2005 international bekannt wurde, als zahlreiche Zeitungen damit begannen, es in ihrer Hobbyabteilung zu veröffentlichen . ]

Das Ziel von Sudoku ist es, ein 9 × 9-Zellen- Gitter (81 Zellen), das in 3 × 3-Untergitter (auch „Kästen“ oder „Regionen“ genannt) unterteilt ist, mit den Zahlen 1 bis 9 zu füllen, beginnend mit einigen Zahlen, die bereits in einigen angeordnet sind der Zellen. Die Ausgangsform des Spiels besteht darin, dass es neun differenzierte Elemente gibt, die sich nicht in derselben Reihe, Spalte oder Unterraster wiederholen dürfen. Ein gut geplantes Sudoku kann nur eine Lösung haben und muss mindestens 17 anfängliche Hinweise haben. ​ Die Lösung eines Sudoku ist immer ein lateinisches Quadrat, obwohl die Umkehrung im Allgemeinen nicht zutrifft, da Sudoku die zusätzliche Einschränkung festlegt, dass dieselbe Zahl nicht in einem Unterraster wiederholt werden kann.

Geschichte

Im 18. Jahrhundert schuf der berühmte Schweizer Mathematiker Leonhard Euler ein System von Wahrscheinlichkeiten, um eine Reihe von Zahlen darzustellen, ohne sich zu wiederholen. Aus diesem Grund gilt Euler als Erfinder dieses Spiels. ]

Bereits 1970 veröffentlichte der Verlag Math Puzzles and Logic Problems eine Rubrik namens Number Place , damit dieses mathematische Rätsel zu einem Hobby wurde, obwohl es Jahre später in Vergessenheit geriet.

1984 veröffentlichte die japanische Zeitung Monthly Nikolist einen Hobbyteil mit dem Titel Sūji wa dokushin ni kagiru (数字は独身に限る) „Zahlen müssen eindeutig sein“ (wörtlich dokushin (独身) = „zölibatär, ledig “). Es war Maki Kaji , Präsident von Nikoli , der es benannte. Der Name wurde zu Sūdoku abgekürzt (sū = Nummer, doku = Single). ]

International bekannt wurde es 2005, als mehrere Zeitungen damit begannen, es als Hobby zu veröffentlichen. ]

Regeln und Terminologie

Sudoku wird normalerweise als 9 × 9-Tabelle dargestellt, die aus 3 × 3-Untertabellen besteht, die als „Regionen“ (auch „Boxen“ oder „Blöcke“ bezeichnet) bestehen.

Einige Zellen enthalten bereits Zahlen, bekannt als "vorgegebene Zahlen" (oder manchmal "Hinweise"). Ziel ist es, die leeren Zellen mit jeweils einer Zahl so zu füllen, dass jede Spalte, Zeile und Region die Zahlen 1–9 nur einmal enthält.

Außerdem kommt jede Zahl in der Lösung nur einmal in jeder der drei "Richtungen" vor, daher müssen die "Zahlen alleine stehen", was an den Namen des Spiels erinnert.

Auflösungsmethoden

Das grün markierte Kästchen im 3 × 3-Bereich in der oberen linken Ecke muss eine 7 enthalten.

Die Strategie zur Lösung dieses Rätsels kann als Kombination aus drei Prozessen betrachtet werden: Tracking, Markierung und Analyse.

Punktmarkierungsmuster (zweite Notation)

Verfolgung

Im obigen Beispiel kann der Spieler durch Hin- und Herfahren über die Siebenen, die sich irgendwo auf dem Gitter befinden, alle leeren Felder in der oberen linken Ecke entfernen, die keine 7 enthalten können. Dadurch bleibt nur ein mögliches Feld (grün markiert).

Markiert

Das Scannen endet, wenn keine neuen Nummern entdeckt werden können. An dieser Stelle ist es notwendig, sich auf eine logische Analyse zu konzentrieren. Die meisten finden es nützlich, diese Analyse zu leiten, indem sie Kandidatennummern in den leeren Zellen markieren. Es gibt zwei gängige Schreibweisen: Indizes und Punkte.

In der tiefgestellten Notation werden Kandidatennummern klein in Zellen geschrieben. Der Nachteil ist, dass die Originalrätsel in Zeitungen veröffentlicht werden, die normalerweise nicht viel Platz lassen, um mehr als ein paar Ziffern unterzubringen. Mit dieser Notation erstellen Löser oft eine größere Kopie des Puzzles und verwenden einen spitzen Bleistift.

Die zweite Notation ist ein Punktmuster mit einem Punkt in der oberen linken Ecke, der eine 1 darstellt, und einem Punkt in der unteren rechten Ecke, der eine 9 darstellt. Diese Notation hat den Vorteil, dass sie im ursprünglichen Puzzle verwendet werden kann. Geschicklichkeit bei der Punktplatzierung ist erforderlich, da das Vorhandensein von versetzten Punkten oder unbeabsichtigten Markierungen unvermeidlich zu Verwirrung führt und sie nicht leicht zu entfernen sind, ohne noch mehr Verwirrung zu stiften.

Analyse

Es gibt zwei Hauptansätze:

• Bei der Eliminierung werden Fortschritte erzielt, indem nacheinander Kandidatennummern für eine oder mehrere Zellen eliminiert werden, bis nur noch eine Wahlmöglichkeit übrig bleibt. Nachdem jede Antwort erreicht wurde, sollte ein neuer Scan durchgeführt werden (normalerweise Überprüfung der Wirkung der letzten Zahl). Es gibt eine Reihe von Ausscheidungstaktiken. Eine der häufigsten ist die „nicht übereinstimmende Kandidatenlöschung“. Zellen mit identischen Kandidatennummernkonfigurationen gelten als übereinstimmend, wenn die Anzahl der Kandidatennummern in jeder gleich der Anzahl der Zellen ist, die sie enthalten. Dieser Ansatz mag von Logikpuristen wegen zu viel Trial-and-Error abgelehnt werden, aber er kann schnell zu klaren Lösungen führen.

Idealerweise müssen Sie eine Kombination von Techniken finden , die einige der Nachteile der oben genannten Punkte vermeidet. Das Zählen von Regionen, Zeilen und Spalten kann langweilig werden. Das Eingeben von Kandidatennummern in leere Zellen kann zeitaufwändig sein. Der „Was-wäre-wenn“-Ansatz kann verwirrend sein, wenn er nicht gut organisiert ist. Die Absicht der Frage besteht darin, eine Technik zu finden, die das Zählen und Markieren minimiert.

Eine systematische Analyse von Logik und Lösungstechniken wurde in englischer Sprache veröffentlicht: "Pattern-Based Constraint Satisfaction and Logic Puzzles". ]

Schwierigkeitsgrade

Computerprogramme , die Sudoku-Rätsel lösen, können basierend auf der Komplexität der erforderlichen Lösungstechniken abschätzen, wie schwierig es für einen Menschen ist, die Lösung zu finden. Diese Schätzung ermöglicht es Verlagen, ihre Rätsel für Personen mit unterschiedlicher Lösungserfahrung zuzuschneiden. Einige "Online"-Versionen bieten auch verschiedene Schwierigkeitsgrade.

Konstruktion

Ein Sudoku muss eine einzige Lösung haben, um als gut formuliert zu gelten; Das heißt, ausgehend von den anfänglichen Hinweisen kann es nur einen gültigen Weg geben, die verbleibenden Zellen auszufüllen. Damit ein Sudoku eine einzige Lösung hat, muss die Anzahl der anfänglichen Hinweise mindestens 17 betragen; dies wurde 2012 gezeigt. ]

Die Konstruktion eines Sudoku-Rätsels kann effizient von Hand erfolgen, indem die Positionen der gegebenen Zahlen vorbestimmt und ihnen Werte zugewiesen werden, um einen deduktiven Prozess durchzuführen.

Nikoli - Sudoku -Rätsel werden von Hand erstellt, und der Name des Autors erscheint im Abspann neben jedem Rätsel ; Die angegebenen Zahlen werden immer in Form eines symmetrischen Musters gefunden. Die Number Place Challenger - Rätsel von Dell (siehe Varianten unten) zitieren ebenfalls Autorennachweise. Die Sudoku-Rätsel, die in den meisten britischen Zeitungen erscheinen, sind anscheinend computergeneriert, aber sie verwenden Wahrscheinlichkeiten in computergenerierten Sudoku-Rätseln. Die Herausforderung für Sudoku-Programmierer besteht darin, einem Programm beizubringen , wie man intelligente Rätsel auf eine Weise baut, die von denen, die von Menschen gemacht werden, nicht zu unterscheiden sind; Wayne Gould brauchte sechs Jahre, um seine beliebte Show zu optimieren, um zu glauben, dass er dieses Niveau erreicht hatte.

Varianten

Obwohl die Tabelle am häufigsten eine Größe von 9x9 mit 3x3-Bereichen hat, gibt es zahlreiche Variationen. Starterspiele können 4x4-Bretter mit 2x2-Regionen sein; Unter dem Namen Logi-5 wurden 5x5-Tabellen mit Pentominos als Regionen veröffentlicht; Die World Puzzle Championship hat eine 6x6-Tabelle mit 2x3 Regionen und eine 7x7-Tabelle veröffentlicht, die aus 6 Regionen besteht, die aus Heptominos und einer separaten Region bestehen. Größere Tabellen können auch gefunden werden. Die Zeitung Times schlägt das Dodeka-Sudoku vor , einen 12x12-Tisch mit 12 4x3-Regionen. Dell Magazine veröffentlichen häufig 16x16-Sätze (die 16x16-Variante verwendet normalerweise die Symbole 1 bis G und nicht die Symbole 0 bis F, die im Hexadezimalformat verwendet werden ). Der Nikoli-Puzzle-Editor schlägt das 25x25 Riesen-Sudoku vor.

Ein Sudoku-Puzzle aus Nonominos ( Polyominos mit 9 Zellen ), wie die in The Sunday Telegraph

Die Lösung des vorherigen Rätsels sind die roten Zahlen

Eine weitere gängige Variante besteht darin, neben der Beibehaltung der normalen Anforderungen an Zeilen, Spalten und Regionen Beschränkungen für die Platzierung von Zahlen hinzuzufügen. Grenzen nehmen oft die Form einer zusätzlichen "Dimension" an; Am gebräuchlichsten ist es, die Eindeutigkeit der Zahlen auf der Hauptdiagonale der Tabelle zu erzwingen. Die bereits erwähnten Number Place Challenger- Spiele beinhalten diese Variante. Ebenfalls Teil dieser Variante sind die Daily Mail- Spiele , die 6x6-Tische verwenden.

Die amerikanische Zeitung USA Today veröffentlicht eine weitere Variante namens "Mini Sudoku", bestehend aus einer 6x6-Tabelle mit 3x2 Regionen. Das Ziel ist das gleiche wie beim Original-Sudoku, aber in dieser Variante werden nur Zahlen von 1 bis 6 verwendet.

Eine weitere Variante ist die Kombination von Sudoku und Kakuro in einem 9x9-Tisch, Kreuzsummen-Sudoku genannt, bei dem die Hinweise durch Kreuzsummen gegeben werden. Es ist auch möglich, dass die Hinweise durch Kryptoarithmen gegeben werden, bei denen jeder Buchstabe eine einzelne Ziffer von 0 bis 9 darstellt. Ein Beispiel ist: ZAHL+ZAHL=KAKURO, dessen einzige Lösung 186925+186925=373850 ist. Ein weiteres Beispiel ist SUDOKU=IS*FUNNY, dessen Lösung 426972=34*12558 ist.

Ein Sudoku- Killer .

Lösung des Rätsels oben.

Addoku kombiniert Elemente von Sudoku und Kakuro – normalerweise werden keine Startnummern vorgegeben, stattdessen wird die 9x9-Tabelle in Regionen unterteilt, die jeweils die Summe aller Zahlen in der Region enthalten, wobei zu berücksichtigen ist, dass sich keine Zahlen in derselben Region wiederholen. Auch beim Ausfüllen der Tabelle werden die Regeln des ursprünglichen Sudoku beibehalten.

Eine der beliebtesten Varianten ist Hypersudoku . Es wird in Zeitungen und Zeitschriften auf der ganzen Welt veröffentlicht und ist auch bekannt für „NRC Handelsblad Sudoku“, „Windoku“, „Hyper-Sudoku“ und „4-Frame-Sudoku“. Die Basis ist identisch mit der des ursprünglichen Sudoku, enthält jedoch zusätzliche innere Bereiche, in denen Zahlen von 1 bis 9 erscheinen müssen.Der Algorithmus, der es löst, unterscheidet sich geringfügig vom normalen Sudoku aufgrund des Einflusses der überlappenden Quadrate. Diese Überlappung gibt dem Spieler mehr Informationen, die es ihm ermöglichen, die Chancen der verbleibenden Frames einzugrenzen. Die Spielweise ähnelt der von Sudoku, jedoch muss man mehr auf die Quadrate und die Überlappungsbereiche achten als auf die Reihen und Spalten.

Ein Buchstaben-Sudoku

Die Lösung des vorherigen ist rot

Spiele, die aus mehreren Sudoku-Brettern bestehen, sind ebenfalls üblich. In Japan ist Sudoku Gattai 5 (Mix of 5) bekannt, das aus 5 9x9-Tischen besteht, die sich in den Eckbereichen in Form eines Quincunx überlappen . In Zeitungen wie The Times oder The Sydney Morning Herald ist diese Variante als Sudoku Samurai bekannt . Andere wie die Baltimore Sun und der Toronto Star veröffentlichen diese Variante in ihrer Sonntagsausgabe unter dem Namen High Five . In den Überlappungsbereichen sind oft keine Hinweise gegeben. Es werden auch Varianten mit sequentiellen statt überlappenden Tabellen veröffentlicht, bei denen die Werte bestimmter Positionen von einer Tabelle auf eine andere übertragen werden.

Social Sudoku ist eine digitale Multiplayer-Version von Sudoku, die es 2 Spielern ermöglicht, gleichzeitig auf demselben Brett zu spielen. Diese Variante wurde 2010 von Crosswords Ltd. erstellt und über das Game Center als App für Apples iOS -Plattform veröffentlicht . Social Sudoku [2] vergibt Punkte an jeden Spieler, wenn er die Zahlen richtig platziert und das ausgewählte Feld für den anderen Spieler blockiert. Falsche Züge führen dazu, dass der Spieler 10 Sekunden lang keinen Zugang zum Brett hat und Punkte verliert.

Es sind auch alphabetische Varianten entstanden, die manchmal als Buchstaben-Sudokus ( Wordokus ) bezeichnet werden: Es gibt keinen funktionalen Unterschied, es sei denn, die Buchstaben bilden Wörter. Einige Varianten, wie die in TV Guide , enthalten ein Wort auf der Hauptdiagonale, in einer Reihe oder in einer Spalte, sobald das Spiel gelöst ist; Die Bestimmung des Wortes im Voraus kann eine Hilfe bei der Auflösung des Spiels sein. Ein Wordoku kann neben dem Hauptwort auch andere Wörter enthalten. Wie im Beispiel rechts könnten die Wörter „Kari“, „Park“ und „Per“ Teil der Lösung sein. Dies sollte vermieden werden, indem beispielsweise das Zeichen „R“ durch das Zeichen „Q“ ersetzt wird. Auf der anderen Seite erlaubt Ihnen Ripeto Sudoku , Symbole zu wiederholen, und benutzerdefiniertes Sudoku zeigt Wörter auf dem Brett, bevor Sie sie lösen.

Benutzerdefiniertes Sudoku mit einem Wort und wiederholten Buchstaben

Eine weitere Variante ohne funktionalen Unterschied ist das Quadratum Latinum mit römischer Nummerierung von Hebdomada Aenigmatum , Luca Desiatas rein lateinischem Kreuzworträtsel-Magazin . ]

Mit einem Standard-Deck mit 81 Spielkarten aus dem Set! Sudoku kann gespielt werden. Die dreidimensionale Version von Sudoku wurde von Dion Church erfunden und im Mai 2005 im Daily Mail Telegraph veröffentlicht. Es gibt auch eine Version des Zauberwürfels namens Cuboku .

Ein Beispiel für Greater Than Sudoku .

Es gibt noch viele andere Varianten. Einige weisen unterschiedliche Formen im Layout der 9x9-Brettüberlappungen auf, wie z. B. einen Schmetterling, eine Windmühle oder eine Blume. Andere Versionen unterscheiden sich in der Auflösungslogik des Spiels. Eines davon ist Greater Than Sudoku . In dieser Version enthält jede 3x3-Region 12 größer als (>) oder kleiner als (<) Symbole auf der gemeinsamen Linie von zwei benachbarten Zahlen. Eine weitere Variante dieser Art ist das Clueless Sudoku , bei dem neun 9x9-Sudoku-Bretter in einer 3x3-Matrix platziert werden. Die mittlere Zelle jeder 3x3-Region in jeder der 9 Tabellen bleibt leer und bildet ein 10. Sudoku ohne vollständige Zellen; daher der Name "ahnungslos". ]

Siehe auch

• Algorithmen zum Lösen von Sudokus
• magisches Quadrat