Sudoku

UR1-Regel: in der Konfiguration (wo die vier Zellen ein Rechteck bilden, das sich über zwei Zeilen, zwei Spalten und nur zwei Blöcke erstreckt):

ab ab

ab abc

Eliminiere a und b aus der letzten Zelle.

UR2-H-Regel: in der Konfiguration (wo die vier Zellen ein Rechteck bilden, das sich über zwei Zeilen, zwei Spalten und nur zwei Blöcke erstreckt):

ab abc

ab abc

wenn sich die beiden rechten Zellen im selben Block befinden, eliminiere c aus allen anderen Zellen, die sich auf die beiden rechten Zellen beziehen.

Es gibt viele Variationen dieser Regeln.

Klassifizierung von Problemen

Es gibt keine universelle Klassifikation der verschiedenen Probleme: Jede Klassifikation basiert auf der Wahl einer Reihe von Lösungsmethoden. Wir können jedoch zwischen Klassifikationen mit großer Reichweite (SER, SXT, NRCZT,  etc. ) und Klassifikationen in vier oder fünf Stufen (von „einfach“ bis „teuflisch“), wie sie in Zeitungen veröffentlicht werden, unterscheiden. Letztere decken meist nur relativ einfache Probleme ab, mit SERs nicht mehr als 5 oder 6.

Es sollte beachtet werden, dass jede Klassifizierung nur ein Hinweis ist und dass für einen Spieler zwei Probleme mit dem gleichen Wert in einer Klassifizierung sehr unterschiedliche Schwierigkeiten bereiten können.

Präambel zu minimalen Problemen und Klassifizierungsstatistiken von Rätseln

Ein aus theoretischer Sicht sehr nützlicher allgemeiner Begriff ist der des minimalen Problems . Ein Problem wird als minimal (oder seltener "lokal minimal") bezeichnet, wenn es eine eindeutige Lösung hat und wenn jedes Mal, wenn wir versuchen, etwas Enthülltes wegzunehmen, das erhaltene Rätsel (das offensichtlich immer mindestens eine Lösung hat) . ) hat am Ende mehrere Lösungen.

Wenn wir Statistiken über die Klassifikation von Problemen erstellen möchten, müssen wir uns immer auf Mengen von minimalen Rätseln beziehen, sonst haben diese Statistiken nicht viel Bedeutung: In der Tat, indem Sie so viele aufgedeckte hinzufügen, wie wir möchten, wählen Sie unter den Lösungswerten mit a minimales Puzzle, man kann sehr viele Puzzles erhalten, die offensichtlich die gleiche Lösung haben, von denen die meisten trivial zu lösen sind.

Beachten Sie, dass es sehr einfach und schnell ist, zufällige Sätze von Tausenden von minimalen Problemen mit dem Computer zu erstellen (z. B. mit der kostenlosen Software suexg (weitere Informationen zum Erstellen von Rätseln siehe unten).

Minimalität ist eine zusätzliche Anforderung, die manchmal vom Ersteller von Problemen erwartet wird. Es hat keine Auswirkungen auf den Spieler. Es kann jedoch schwierig sein, mit anderen zusätzlichen Anforderungen, wie beispielsweise ästhetischen Anforderungen, beispielsweise der Symmetrie, in Einklang zu kommen, nämlich dass sich die freigelegten in einem Satz von Zellen mit einer bestimmten Symmetrieform befinden. Es ist schwieriger, Probleme zu erzeugen, die sowohl minimal sind als auch bestimmte Symmetrien aufweisen (insbesondere bei suexg nicht).

Im Laufe des Jahres 2008 stellte sich heraus, dass die klassischen Generatoren von minimalen Problemen, egal ob sie "  bottom-up  " oder "  top-down  " sind (das heißt, sie beginnen von einem leeren Raster aus und füllen es nach und nach auf oder beginnen von ein volles Raster und eliminiere Hinweise nacheinander) waren alle stark voreingenommen zugunsten von Problemen mit wenigen Hinweisen. Eine neue Art von Generator wurde eingeführt: Bias-gesteuerte Generatoren. Auch sie sind voreingenommen, aber ihre Voreingenommenheit ist bekannt und kann daher korrigiert werden. Siehe eines der beiden Bücher Constraint Resolution Theories , Pattern-Based Constraint Satisfaction and Logic Puzzles oder den auf der Website des Autors verfügbaren Artikel Unbiased Statistics of a CSP - A Controlled-Bias Generator .

SER ( Sudoku-Erklärer-Bewertung )

Das SER ( Sudoku Explainer Rating ) ist die mit Abstand am häufigsten verwendete Klassifizierung. Sudoku Explainer ist eine kostenlose Software (in Java), die von Nicolas Juillerat entwickelt wurde und aus dem Internet heruntergeladen werden kann. Es kann verwendet werden, um Probleme zu lösen, aber auch um eine Schätzung ihrer Schwierigkeit zu erstellen, die als SER bezeichnet wird. Dieser nimmt Werte von 1 bis 11,7 (bisher bekannter Höchstwert) an.

Die verwendeten Regeln (von denen einige auf der Annahme der Eindeutigkeit basieren) sind ziemlich heterogen und die Werte werden ziemlich ad hoc zugewiesen . Zur Veranschaulichung sind hier die Ebenen, die einigen der oben definierten Regeln zugeordnet sind.

• 1.0 bis 2.3 Verschiedene Singletons
• 3.0 Nackte Paare
• 3.4 Versteckte Paare
• 3.6 Nackte Drillinge
• 3.8 Schwertfisch
• 4.0 Versteckte Drillinge
• 5.0 Nackte Vierlinge
• 5.2 Quallen
• 5.4 Versteckte Vierlinge

Die höheren Ebenen verwenden verschiedene Arten von Ketten:

• 11.6 Dynamische + Dynamische Forcing-Ketten ( 145-192 Knoten ) Cell-Forcing-Ketten
• 11.7 Dynamische + Dynamische Zwangsketten ( 193-288 Knoten ) Doppelte Zwangsketten

Diese dynamischen Zwangsketten sind eine Form von Versuch und Irrtum.

Die Klassifikation der schwierigsten Probleme basiert im Wesentlichen auf der Anzahl der elementaren Schlussfolgerungen, die für die schwierigste Eliminierung im Rahmen eines Trial-and-Error-Verfahrens auf bis zu zwei Ebenen erforderlich sind (d. h., Annahmen über maximal zwei Kandidaten gleichzeitig zu ermöglichen) . Hier bedeutet elementare Inferenz entweder ein Singleton (nackt oder versteckt) oder die Eliminierung eines Kandidaten in direktem Widerspruch mit einem oder zwei bekannten oder vermuteten Werten durch Versuch und Irrtum.

NRCZT-Klassifizierung

Diese in The Hidden Logic of Sudoku definierte Klassifikation basiert auf der maximalen Länge des nrczt-Strings, die zur Lösung eines Problems benötigt wird. Im Gegensatz zum SER wird hier nur ein Regeltyp (die nrczt-Strings unterschiedlicher Länge) verwendet und diese Klassifikation, rein logisch, unabhängig von der Annahme der Eindeutigkeit und unabhängig von jeglicher Implementierung, ist mit allen Symmetrien des Spiels kompatibel.

Obwohl sie auf Regeln basiert, die sich daher stark von denen der Basis des SER unterscheiden, ist diese Klassifikation eng mit dieser korreliert: Eine Studie an 10.000 verschiedenen Minimalproblemen (erhalten mit dem Pseudo-Zufallsgenerator suexg) liefert einen Korrelationskoeffizienten a von 0,89. Dies bedeutet, dass diese beiden Klassifikationen einen wichtigen Aspekt der Komplexität eines Problems erfassen.

Die Statistiken der nrczt-Klassifikation sind verfügbar:

- in drei Büchern: The Hidden Logic of Sudoku , Constraint Resolution Theories and Pattern-Based Constraint Satisfaction and Logic Puzzles

- und in zwei Artikeln desselben Autors: From Constraints to Resolution Rules, Part II : chain, Braids, confluence and T&E (basierend auf 10.000 minimalen zufälligen Problemen) und Unbiased Statistics of a CSP - A Controlled-Bias Generator .

Die folgenden Ergebnisse basieren auf dem neuen vorspannungsgesteuerten Generator (und fast sechs Millionen zufälligen Minimalproblemen); sie sind unvoreingenommen. Dieser Generator und die umfangreiche zugehörige Sammlung sind auf der GitHub-Plattform zugänglich: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection

Der Sudokus-Resolver, mit dem diese Klassifizierung erstellt wurde (SudoRules, Teil der allgemeineren CSP-Rules-Constraint-Resolution-Software) ist auf der GitHub-Plattform zugänglich: https://github.com/denis-berthier/CSP-Rules-V2 .1

Die prozentuale Verteilung nach nrczt-Stufen ist wie folgt:

• Stufe 0: 29,17
• Stufe 1: 8,44
• Stufe 2: 12.61
• Stufe 3: 22.26
• Stufe 4: 21.39
• Stufe 5: 4,67
• Stufe 6: 1,07
• Stufe 7: 0,29
• Stufe 8: 0,072
• Stufe 9: 0,020
• Stufe 10: 0,005 5
• Stufe 11: 0,001 5

In dem Wissen, dass die effektive Komplexität eines Problems mit seinem SER oder seinem NRCZT fast exponentiell wächst, zeigen diese Zahlen Folgendes:

1) eine sehr große Mehrheit der Probleme kann durch relativ einfache Techniken (hier kurze Ketten) gelöst werden;

2) trotz allem bleiben sehr komplexe Probleme bestehen, die es rechtfertigen, dass erfahrene Spieler ständig nach neuen Regeln suchen, die es ermöglichen, die mit den bisher bekannten Regeln erhaltenen Lösungen zu vereinfachen;

3) Außergewöhnlich komplexe Probleme (wie das berüchtigte Ostermonster ) werden sehr unwahrscheinlich von einem Zufallsgenerator gefunden und einige Spieler versuchen ständig, neue Beispiele "von Hand" zu erstellen.

Kollaterale Ergebnisse: Die Technik der kontrollierten Bias-Generatoren ermöglicht es auch, die Anzahl der minimalen Probleme (3,10 × 10 ^ 37) sowie die Anzahl der nicht äquivalenten minimalen Probleme (2,55 × 10 ^ 25) abzuschätzen.

Klassifikationen von Problemen der "allgemeinen Öffentlichkeit"

Die meisten Autoren von Sudoku-Lehrbüchern sind sich einig, dass mehrere Faktoren die Schwierigkeit dieser Probleme beeinflussen, deren Grundgleichung modulo eine bestimmte Gewichtung berücksichtigt :

• die Anzahl der auszufüllenden Zellen;
• die Anzahl der durch Eliminierung gefüllten Zellen;
• die Anzahl unabhängiger Gruppen von numerisch verknüpften Vielfachen, die entlang einer einzigen Dimension behandelbar sind; Region, Zeile oder Spalte;
• die Anzahl unabhängiger Gruppen numerisch verknüpfter Vielfacher, die gleichzeitig in zwei Dimensionen behandelbar sind; Region × Zeile, Region × Spalte oder Spalte × Zeile;
• die Anzahl unabhängiger Gruppen numerisch verknüpfter Vielfacher, die gleichzeitig in allen drei Dimensionen behandelbar sind; Bereich × Zeile × Spalte;
• die Anzahl der Annahmen, die im Falle einer vorübergehenden Blockade zu treffen sind;
• die Anzahl der Iterationen der Lösungsheuristik ;
• die Anzahl der durchzuführenden Suchen, um das Raster zu vervollständigen.

Dieses Problem der Schwierigkeit ist jedoch in Sudoku-Foren immer noch Gegenstand vieler Debatten, da es sich auf die Konzepte und visuellen Darstellungen bezieht, die jeder gerne annehmen möchte. Aber es lässt sich vollständig erklären, wenn wir von einfach bis komplex die Techniken und Verfahren priorisieren, mit denen wir in einem Raster erfolgreich sein können, und wenn wir unsere Spielweise berücksichtigen (beachten Sie bestimmte Handicap-Regeln, wie z nur mentales Denken, oder das absolute Verbot, das Gitterproblem in mehreren Gittern durch Annahmen zu reproduzieren  usw. ).

Aber wir dürfen das Niveau des Spielers nicht mit dem Schwierigkeitsgrad eines Gitters verwechseln. Manche Spieler sind in der Lage, ein Raster durch mentales Denken zu bestehen, ohne ein Vielfaches in die Kästchen zu schreiben, die dann nur die richtige Zahl erhalten, während andere mit Kästen kämpfen, die mehrere Kandidaten präsentieren, oder mit mehreren Rastern, von Hypothesen, die kostenlos erstellt oder entsprechend entwickelt wurden zu Kategorien (Zeilen, Spalten und Regionen) einschließlich des gemeinsamen Rasters, das tatsächlich eine bestimmte erweiterte Auflösungstabelle enthält. Aus diesem Grund klassifizieren wir die Problemgitter lieber in fünf Typen, innerhalb derer wir unterschiedliche Schwierigkeitsgrade finden:

Verwendung einfacher Techniken, einschließlich "Finden des richtigen Kästchens für eine gegebene Zahl und Region" durch Kreuzreduktion und "Finden der richtigen Zahl für eine bestimmte Zelle" durch Zählen, obwohl letzteres etwas mühsamer ist als das erste. Im Prinzip wird bei dieser Art von Raster gedanklich argumentiert, ohne die möglichen Kandidaten in einer bestimmten Zelle registrieren zu müssen, und das Füllen des Rasters erfolgt schrittweise, indem man einer der unzähligen Spuren oder Sequenzen folgt, die sich ergeben. Es sind diese Art von Rastern, die Sie häufig in Websites, Zeitungen und Zeitschriften finden oder von Software erstellt werden und einige von ihnen fälschlicherweise in die Kategorie "schwierig" oder sogar "teuflisch" einordnen! Der Grund dafür ist, dass es eine Klasse von Typ-1- Gittern gibt , die durch Kopfrechnen wirklich schwer zu passieren sind. Unterschätzen Sie daher nicht die Raster des Typs 1  : Es gibt "leichte", "mittel" und sogar "schwierige" Raster .

Verwendung von Techniken, die die Verarbeitung von Zellen mit mehreren Kandidaten in einer einzigen Dimension ermöglichen; Reihe, Spalte oder Region, einschließlich „Strippen wegen nackter Paare“, „Durchsuchen versteckter Kandidaten“ und „Durchsuchen von getarnten Paaren“. Einige Typ-2- Raster können mental erfolgreich sein, wie Typ 1 . Andere, auf einer höheren Ebene, verlangen, dass wir die Kandidaten in den Zellen einer Region, einer Zeile oder einer Spalte registrieren, ohne dies jedoch für alle leeren Zellen zu tun, und zu sehen, ob wir die Vielfachen um . vereinfachen können eine der drei vorherigen Techniken. Die schwierigeren Gitter dieses Typs 2 eignen sich nicht zum Lösen, bis alle Zellen ihre wahrscheinlichen Kandidaten enthalten. In diesem Fall müssen wir versuchen, die optimale Situation des Rasters zu erreichen: In jeder Kategorie (Zeile, Spalte und Region) müssen die Gruppen der „numerisch verknüpften Vielfachen“ „unabhängig“ sein. Andere einfache eindimensionale Verarbeitungstechniken können verwendet werden, einschließlich „Strippen wegen bloßer Drillinge“ und „Entfetten von getarnten Drillingen“. Letzteres ist schmerzhafter! Wir können auch bestimmte Zahlen durch eine einfache Verarbeitungstechnik eliminieren, diesmal in zwei Dimensionen Zeile × Region oder Spalte × Region: "die Verteilung eines Blocks in vier komplementäre oder alternierende Domänen". Wenn Sie sich also für eine mentale Übung entscheiden, bietet Ihnen diese Art von Raster einige sehr schwierige. Und wenn Sie sich erlauben, die Vielfachen in die Zellen zu schreiben, haben Sie einige sehr schöne Übungsaufgaben im Umgang mit "unabhängigen Gruppen von numerisch verknüpften Vielfachen".

Verwendung von Techniken, die die Vereinfachung von Zellen mit mehreren Kandidaten ermöglichen, zunächst wie für Typ 2 , gemäß einer einzigen Dimension; Zeile, Spalte oder Region, jedoch mit einer größeren Größe, einschließlich "Eliminierung aufgrund von bloßen Quads und Quinteln" und "Entfettung von versteckten Quads und Quinteln". Um mit dieser letzten Technik fortzufahren, die außerdem mühsamer durchzuführen ist, muss man "die Eliminierung wegen einer oder zwei nackter Gruppen" verwenden, aber von geringerer Größe!

Einige Gitter vom Typ 3 erfordern eine Behandlung in zwei Dimensionen (Reihen × Spalten, Reihen × Regionen und / oder Spalten × Regionen) mit viel clevereren, aber vertretbaren Verfahren, einschließlich X-Wing, Swordfish , Jellyfish , Squirmbag oder der TPU, der Technik, die sich von ableitet das "Prinzip der Einzigartigkeit der Lösung". Für diese Art von Gitter sollten wir also nicht hoffen, nur durch mentale Überlegungen zur Lösung zu gelangen, ohne fortan alle möglichen Kandidaten in alle Zellen gestellt zu haben. Je nach Größe der nackten oder getarnten Gruppen, aber auch nach Anzahl sind drei Schwierigkeitsgrade möglich.

Die Strategie für solche Raster, die komplexere Fälle darstellen, besteht darin, gleichzeitig die drei Dimensionen (Zeilen × Spalten × Regionen) zu berücksichtigen. Es ist daher notwendig, durch die Kästchen von einer Region zur anderen zu "springen", indem "Gateways" verwendet werden, die entweder durch eine Reihe, eine Spalte oder einen Bereich materialisiert werden. Kurz gesagt, Sie müssen "Pfade" zwischen den verschiedenen Boxen erstellen. Somit werden wir ähnliche Prozesse erkennen, die bereits von der zweidimensionalen Verarbeitung verwendet werden, einschließlich beispielsweise des X-Wings (die Scheitelpunkte sind nicht mehr die eines Rechtecks, sondern die eines Polygons). Beachten Sie, dass diese Strategie auf einer bivalenten Logik basiert (für eine feste Zahl N und eine gegebene Box von Vielfachen p: „N ist der Wert“ oder nicht (p: „N ist nicht der Wert“).

Aus einem bestimmten Blickwinkel betrachtet geht es darum, zwei oder mehr Gitter auf das gleiche Ausgangsgitterproblem zu überlagern, eine logische Konjugation der verschiedenen (durch Pfade konkretisierten) Sätze vorzunehmen und diejenigen der Gitter zu bestimmen, die zu einem Widerspruch führen mit einer der Regeln, die das Sudoku-Spiel bestimmen, um die richtige Lösung zu finden. Es ist also, als ob wir hypothetisch formulieren, aber auf Umwegen! Wir müssen zugeben, dass diese Vorgehensweise mehr Spaß macht zu spielen und Verfahren anzuwenden, als Hypothesen aufzustellen, um auf intellektueller Ebene „schlechte“ Tische zu erhalten! Verwenden Sie Farbstifte. Diejenigen, die bereits in diese Technik eingeweiht sind, werden leichte, mittlere und sogar schwierige Raster erkennen.

Einige Zeitungen, Zeitschriften, Websites und Software liefern sogenannte "teuflische" oder sogar "höllische" Raster. In den meisten Fällen können diese Gitter mit bis heute entwickelten Techniken gelöst werden und sind viel weniger schwierig, als es den Anschein hat. Tatsächlich ist ein diabolisches Raster eines, das mit keinem der bisher entwickelten Verfahren gelöst werden kann, außer durch die Formulierung einer oder mehrerer Hypothesen über die Zahlen, die in ein oder mehrere Kästchen gesteckt werden sollen. Natürlich ist die Eindeutigkeit der Lösung für das Raster erforderlich.

Nur so ist von nun an eine Lösung zu erreichen, während auf die Entwicklung neuer „manueller“ Prozesse gewartet wird.

Schließlich sollten wir darauf hinweisen, dass es beim Konstruieren von Problemgittern oft einfacher ist, ein Gitter vom Typ 1 zu erhalten , und fast selten ein Gitter vom Typ 4 oder 5 zu finden . Die bisher entwickelte Software geht natürlich von den verschiedenen Lösungsmethoden aus, um ein Problem zu fabrizieren, aber das gewünschte Niveau sinkt in der Regel um ein oder sogar zwei Grad. Statistisch stellen wir fest, dass die Häufigkeitsverteilung nach Typ etwa 46 %, 32 %, 11 %, 8 % und 3 % beträgt, vom ersten Typ bis zum fünften.

Computer und Sudoku

Softwarelösungen

Für einen IT-Profi ist die Programmierung der Lösungssuche durch Eventualitäten oder Mehrfachkontingenzen (wie für die schwierigsten Probleme erforderlich) eine relativ einfache Aufgabe. Ein solches Programm imitiert einen menschlichen Spieler, der nach einer Lösung sucht, ohne auf den Zufall zurückzugreifen.

Es ist auch relativ einfach, einen Backtracking-Suchalgorithmus zu entwerfen . Normalerweise reicht es aus, wenn der Algorithmus 1 für die erste Zelle wählt, dann 2 für die nächste, und so weiter, solange kein Widerspruch auftritt. Wenn ein Widerspruch auftritt, versucht der Algorithmus einen anderen Wert für die Zelle, die den Widerspruch hervorruft. Sind für diese Zelle alle Möglichkeiten ausgeschöpft, „geht der Algorithmus zurück“ und beginnt wieder mit der vorletzten Zelle.

Obwohl dieser Algorithmus nicht sehr elegant ist, findet er sicher eine Lösung, wenn es eine gibt. Ein 9 × 9-Gitter wird normalerweise in weniger als drei Sekunden mit einem modernen Personalcomputer, der einen Interpreter verwendet , und in Millisekunden mit einer kompilierten Sprache gelöst . Es gibt jedoch Gitter, die durch Backtracking besonders schwer zu lösen sind (siehe (in) Algorithmics of Sudoku # Brute-Force-Algorithmus ).

Eine besondere Implementierung von Backtracking ist die Verwendung von Logikprogrammierung , wie sie in Prolog implementiert ist . In diesem Fall stellt der Designer dem Programm die Randbedingungen des Rasters zur Verfügung (eine Zahl pro Zeile, pro Spalte und pro Region; die gezeigten Zahlen); Dieses Programm wird die Entscheidungen treffen, um das Problem zu lösen. Wenn wir zugeben, dass das Netz eine einzigartige Lösung hat, ist die Forschung sicher, erfolgreich zu sein.

Donald Knuth hat einen Algorithmus entwickelt, der doppelt verknüpfte Listen ( tanzende Links ) verwendet und dieser Art von Sudoku in wenigen Millisekunden sehr effektiv löst.

Eine weitere Lösung, die 2007 von dem Formal-Methoden- Forscher Nicolas Rapin vorgeschlagen wurde, besteht darin, den Lösungsraum eines Drahtgestells mithilfe der binären Entscheidungsdiagrammstruktur (kurz BDD) zu lösen und innerhalb einer einzigen Struktur darzustellen. Die Idee besteht darin, das Vorhandensein der Ziffer k in Zeile i , Spalte j durch die boolesche Variable x_i_j_k zu modellieren, indem man als Konvention annimmt, dass der wahre Wert dieser Variablen das Vorhandensein der Ziffer k in Zeile i , Spalte j und die Wert falsch seine Abwesenheit. Sie benötigen also 9 × 9 × 9 boolesche Variablen , um ein 9 × 9-Sudoku-Gitter zu modellieren. Die in Sudoku enthaltenen Einschränkungen können dann direkt in Form von Booleschen Formeln geschrieben und an eine Datenbankbibliothek übergeben werden. Dieser Ansatz hat den Vorteil, nicht nur wohlgeformte Sudoku-Gitter (mit nur einer Lösung) lösen zu können, sondern auch alle Lösungen von schlecht geformten Gittern mit mehreren Lösungen aufzuzählen (die Lösungen sind durch die Pfade des Diagramms gegeben, die zu Blatt 1) ​​oder um zu beweisen, dass ein schlecht geformtes Gitter keine Lösung bietet. Diese Methode kann daher nützlich sein, um Gitter zu lösen, zu entwickeln und zu validieren. Wenn Sie einstellen, dass → die logische Implikation bezeichnet,! Negation und V-Disjunktion, hier ist ein Beispiel für die Regionsbeschränkung: x_1_1_1 →! (x_1_2_1 V x_1_3_1 V x_2_1_1 V x_2_2_1 V x_2_3_1 V x_3_1_1 V x_3_2_1 V x_3_3_1). In natürlicher Sprache bedeutet dieser Ausdruck: Wenn die Zahl 1 in Zeile 1 , Spalte 1 vorhanden ist , dann ist sie an anderer Stelle in ihrem Bereich nicht vorhanden . Die Spaltenbeschränkungen haben die Form x_i_j_k →! ( x_h_j_k), die der Zeile der Form x_i_j_k →! ( x_i_h_k) und das Vorhandensein einer Ziffer für jede Box i, j der Form x_i_j_h. Für die gefüllten Zellen des Gitters werden die obigen impliziten Beschränkungen (Region, Zeile, Spalte) auf die Konsequenz (Term rechts von der Implikation) reduziert, da die Vorgeschichte wahr ist. Während der Implementierung dieser Lösung beobachten wir, dass die allgemeine Effizienz sehr empfindlich auf die Reihenfolge reagiert, in der die Einschränkungen an die Konstruktionsbibliothek des BDD übergeben werden. Auf einem Standard-PC (1,6  GHz , 1  GiB RAM) beträgt die Auflösungszeit für wohlgeformte Raster zwischen 1  s und 2  min  30  s (je nach Raster). Kostenlose Implementierungen sind verfügbar. ∨ha≠ich{\ displaystyle \ vee _ {h \ neq i}}∨ha≠ich{\ displaystyle \ vee _ {h \ neq i}}∨ha∈[1,9]{\ displaystyle \ vee _ {h \ in [1,9]}}

Es gibt auch viele kostenlose Programme im Web, die auf der Implementierung von Regeln basieren, die von Spielern verwendet werden: Sudocue, Sudoku Explainer , Sudoku Susser, Sudoktor, Sadman, der gsf-Solver. Das jetzt öffentlich zugängliche SudoRules-Programm basiert auf Techniken der künstlichen Intelligenz ; es ist Teil einer allgemeineren Software zur Lösung von Problemen bei der Erfüllung von Beschränkungen (die auch andere Logikspiele umfasst). Es ist auf der GitHub-Plattform verfügbar: https://github.com/denis-berthier/CSP-Rules-V2.1 .

Gitterbau

Es scheint, dass die Charts von Dell Magazines , dem Pionier auf dem Gebiet der Veröffentlichung, per Computer erstellt werden. Sie bestehen normalerweise aus 30 zufällig verteilten Zahlen . Der Autor der Raster ist unbekannt. Im Winter 2000 behauptete Wei-Hwa Huang , er sei der Autor des Programms, das diese Gitter erstellt; Ihm zufolge wurden die bisherigen Tore von Hand gebaut. Der Generator wäre in C++ geschrieben und bietet zwar einige Optionen, um den japanischen Markt zu befriedigen ( Symmetrie und weniger Zahlen), Dell zieht es jedoch vor, diese nicht zu verwenden. Einige spekulieren, dass Dell dieses Programm weiterhin verwendet, aber es gibt keine Beweise für ihre Behauptung.

Sudoku-Rätsel von Nikoli , einem großen Sudoku-Hersteller in Japan, werden von Hand gebaut, wobei der Name des Autors bei jedem veröffentlichten Rätsel erscheint; die angaben werden immer symmetrisch dargestellt. Dieser Exploit ist möglich, indem man im Voraus den Ort kennt, an dem sich die Aufdeckung befindet, und anschließend den so ausgewählten Zellen eine Nummer zuweist. Die Nummer Place Challenger Dell zeigt auch den Namen des Autors an. Die in den meisten britischen Zeitungen veröffentlichten Raster würden automatisch erstellt, verwenden jedoch Symmetrie, was bedeuten würde, dass ein Mensch sie erstellt. Der Guardian behauptet, seine Gitter seien von Japanern handgefertigt, aber der Autor wird nicht erwähnt. Sie würden von Leuten aus Nikoli gebaut werden. Der Guardian behauptete, dass sie, da sie von Hand gebaut wurden, höchst unwahrscheinliche "subtile Hinweise" in computererstellten Rastern enthalten.

Es ist möglich, Raster mit mehreren Lösungen oder ohne Lösungen zu erstellen, aber diese werden nicht als echte Sudoku betrachtet. Wie bei vielen anderen Logikspielen ist eine einzigartige Lösung erforderlich. Daher ist beim Erstellen eines Gitters große Sorgfalt erforderlich, da eine einzige falsch platzierte Zahl eine Lösung unmöglich machen kann.

Freie Software (suexg), die es erlaubt, minimale Probleme (mehrere Zehner pro Sekunde) zu erstellen, ist im Web verfügbar.

Minimalität ist eine zusätzliche Anforderung, die manchmal vom Ersteller des Problems erwartet wird, obwohl sie keine Auswirkungen auf den Spieler hat. Es kann schwierig sein, mit anderen zusätzlichen Anforderungen, wie ästhetischen Anforderungen, beispielsweise der Symmetrie, in Einklang zu kommen, nämlich dass sich die freigelegten in einem Satz von Zellen mit einer bestimmten Symmetrieform befinden. Es ist schwieriger, Probleme zu erzeugen, die sowohl minimal sind als auch bestimmte Symmetrien aufweisen (insbesondere bei suexg nicht).

Hinweise und Referenzen

1. https://www.j-platpat.inpit.go.jp/c1800/TR/JPT_5056856/F9A8AC1B402D5E9F6E7B4E7246A6CE85/00/ja
2. http://www.mathpuzzle.com/MAA/41-Sudoku%20Variations/mathgames_09_05_05.html
3. (in) Mark Swaney, Magic Squares .
4. Problem VI "Angenehme und köstliche Probleme, die durch die Zahlen erledigt werden".
5. (de) Sudoku-Anleitung .
6. Jean Robin, "  Der Erfinder des Sudoku ist Franzose  " , auf leparisien.fr ,5. Juni 2006(Zugriffs 1 st Januar 2018 ) .
7. http://www.time.com/time/magazine/article/0.9171,2137423,00.html
8. (fr) http://www.kuboku.com/
9. (in) "  http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoko/sudoku_word.html  " ( Archiv • Wikiwix • Archive.is • Google • Was tun? ) ( Zugegriffen am 30. März 2013 ) .
10. (de) http://sudoku.top-notch.co.uk/wordoku.asp
11. "  Benutzerdefiniertes Sudoku  "
12. (de) http://www.mathrec.org/sudoku
13. (de) http://sudoku.top-notch.co.uk/superwordoku.asp
14. (in) Walter T. Federer. Experimentelles Design: Theorie und Anwendung. Macmillan, New York, 1955, 544 + 47  S.
15. Pierre Dagnelie. Vor dem Sudoku: das magische lateinische Quadrat. Revue Modulad 39, 172-175, 2008 (oder [PDF] ).
16. Magische Quadrate in China .
17. (in) Herkunft in französischen Zeitungen in den 1890er Jahren bis etwa 1930 gefunden , erhoben in einer britischen Zeitung der Times vom 3. Juni 2006.
18. (in) "  http://www.mathsisfun.net/SingleNumber.sit  " ( Archiv • Wikiwix • Archive.is • Google • Was tun? ) (Zugriff am 30. März 2013 ) .
19. (in) "  http://www.mathsisfun.net/SingleNumber.prc  " ( Archiv • Wikiwix • Archive.is • Google • Was tun? ) (Zugriff am 30. März 2013 ) .
20. (in) G2, Heimat des anspruchsvollen Sudoku-Süchtigen , The Guardian , veröffentlicht am 13. Mai 2005.
21. (in) „  Das größte Sudoku-Puzzle der Welt: Gewinnen Sie £ 5000 , Sky One , abgerufen am 28. Mai 2009  “ ( Archiv • Wikiwix • Archive.is • Google • Was tun? ) (Zugriff am 30. März 2013 ) .
22. (in) [PDF] .
23. (en) Denis Berthier , "  The Hidden Logic of Sudoku  " , Lulu Publishers ,16. Mai 2007( ISBN  978-1-84753-472-9 , online gelesen , abgerufen am 16. Mai 2007 ).
24. (ja) http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
25. (de) http://www.csse.uwa.edu.au/~gordon/sudokumin.php
26. (in) Sudoku-Aufzählungsprobleme .
27. Nach A107739 von OEIS .
28. Jean-Paul Delahaye, The Sudoku problem , Pour la Science n o  447, Januar 2015, S.  76-81
29. (in) http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html und nach A109741 von OEIS
30. (ja) プ ロ グ ミ ン グ ズ ル 雑 談 コ ー ナ.
31. (in) Minimum Sudoku .
32. (in) Gary McGuire: Es gibt kein 16-Hinweis-Sudoku-Sudoku, das das Problem mit der minimalen Anzahl von Hinweisen löst [PDF] .
33. Pierre Barthélémy, "  17 ist die Zahl Gottes im Sudoku  " , auf lemonde.fr ,8. Januar 2012(Zugriff am 16. August 2020 ) .
34. Laut (in) SadMan Software: Sudoku Solving Techniques - Naked Single / Singleton / Sole Candidate .
35. Gemäß (in) SudoCue - Sudoku Solving Guide .
36. (in) Denis Berthier From Constraints to Resolution Rules, Part I : Conceptual Framework , International Joint Conferences on Computer , Information , Systems Science and Engineering ( CISSE 08 ), 5.-13. Dezember 2008 .
37. (en) Denis Berthier , "  Constraint Resolution Theories  " , Lulu Publishers ,5. Oktober 2011( ISBN  978-1-4478-6888-0 , online gelesen , abgerufen am 5. Oktober 2011 ).
38. (en) Denis Berthier , „  Pattern-Based Constraint Satisfaction and Logic Puzzles  “ , Lulu Publishers ,20. November 2012( ISBN  978-1-291-20339-4 , online gelesen , abgerufen am 20.11.2012 ).
39. Denis Berthier, Unbiased Statistics of a CSP - A Controlled-Bias Generator , International Joint Conferences on Computer , Information , Systems Sciences and Engineering ( CISSE 09 ), 4.-12. Dezember 2009.
40. Denis Berthier, From Constraints to Resolution Rules, Part II : chain, Braids, confluence and T&E , International Joint Conferences on Computer , Information , Systems Sciences and Engineering ( CISSE 08 ), 5.-13. Dezember 2008 .
41. Siehe (en) Lösung für das Oster-Monster Puzzle: Formale Logik und Zahlenpaar Ketten oder (en) Ostern Monster für eine Studie über die „  Ostern Monster  “ Lösung.
42. (de) Knuth: Vordrucke .
43. "  Robdd-basierter Sudoku-Löser  "

Siehe auch

Literaturverzeichnis

• Narendra Jussien, Précis de Sudoku , Hermès Lavoisier, 2006, 188 Seiten ( ISBN  2-7462-1559-4 ) .
• (en) Denis Berthier, The Hidden Logic of Sudoku , Lulu Publishers  ; 1 st  Ausgabe,Mai 2007, 384 Seiten ( ISBN  978-1-84753-472-9 )  ; zweite Ausgabe,November 2007, 416 Seiten ( ISBN  978-1-84799-214-7 ) .
• (en) Denis Berthier, Constraint Resolution Theories , Lulu Publishers ,November 2011, 308 Seiten ( ISBN  978-1-4478-6888-0 ) .
• (en) Denis Berthier, Pattern-Based Constraint Satisfaction and Logic Puzzles , Lulu Publishers ,November 2012, 484 Seiten ( ISBN  978-1-291-20339-4 ) .
• "Das Sudoku Tsunami", Pour la Wissenschaft , n o  338,Dezember 2005, s.  144 .
• (en) Denis Berthier, From Constraints to Resolution Rules, Part I : Conceptual Framework , International Joint Conferences on Computer , Information , System Sciences and Engineering ( CISSE 08 ), 5.-13. Dezember 2008 ; als Kapitel des Buches Advanced Techniques in Computing Sciences and Software Engineering , Springer, 2010 ( OCLC 5662041121 ) wiederveröffentlicht .
• (en) Denis Berthier, From Constraints to Resolution Rules, Part II : chain, Braids, confluence and T&E , International Joint Conferences on Computer , Information , Systems Sciences and Engineering ( CISSE 08 ), 5.-13. Dezember 2008 ; als Kapitel des Buches Advanced Techniques in Computing Sciences and Software Engineering , Springer, 2010 ( OCLC 5661887312 ) wiederveröffentlicht .
• (en) Denis Berthier, Unbiased Statistics of a CSP - A Controlled-Bias Generator , International Joint Conferences on Computer , Information , Systems Sciences and Engineering ( CISSE 09 ), 4.-12. Dezember 2009 ; wiederveröffentlicht als Kapitel des Buches Innovations in Computing Sciences and Software Engineering , Springer, 2010 DOI : 10.1007 / 978-90-481-3660-5_28 .

Zum Thema passende Artikel

• Französischer Sudoku-Verband
• Sudoku Math

• Pfeilnummern
• Lateinisches Quadrat
• Geometrische Rätsel .

• Michael Mepham
• Wayne Gould
• Nikolai
• Dell Zeitschriften
• Patrick Maignan und Alain Duverger Autoren des Kalkudo-Spiels (2009 erfundenes Kreuzrechnungsspiel mit sechs Schwierigkeitsgraden www.kalkudo.fr)

Externe Links

• Über die plötzliche Popularität von Sudoku in Großbritannien:
  • (de) "  Die rätselhafte Popularität von Su Doku  " , BBC News ,22. April 2005.
  • (de) „  Du dachtest also, Sudoku käme aus dem Land der aufgehenden Sonne…  “ , The Observer ,15. Mai 2005.