Wie löse ich das härteste Sudoku der Welt '?

Erraten einzelner Werte bei einer Tiefensuche ist nicht optimal.

Hier ist also eine Argumentationskette, die auf einer Hypothese / Disproof-Methode basiert (die mein Stiefsohn widerstrebend als „fundiertes Raten“ bezeichnet).

Nur der Kette zu folgen, einschließlich Widersprüchen Um 23 Varianten des Sudoku zu lösen, wird es am besten mit einem computergestützten Löser verwendet. Es sind jedoch keine ausgefallenen Algorithmen erforderlich, um ihm zu folgen. (Ich verwende mein eigenes, nicht optimiertes Python-Programm, daher gibt es kein echtes Computing Macht beteiligt entweder).

Die Notation folgt Tabellenkalkulationskonventionen (Spalte = Buchstabe, Zeile = Zahl) (oder Schach, wenn Sie so wollen).

STA Original Sudoku G8: 3,9 HYP # I8: 3,9 DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 STA # I8: 3,9 + B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 STA # I8: 3,9 + B1: 6 + A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 STA I8: 2,7 HYP I8: 2,7 # G7: 5 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 STA I8: 2,7 # G7: 5 + G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 STA I8: 2,7 + G7: 3,9 HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL 

Ich habe Screenshots der Schritte und eine kurze Erklärung der Methode unter Das härteste Sudoku der Welt erstellt. Da ich nur daran interessiert bin, schwierige Rätsel durch „fundiertes Raten“ zu lösen, stellte ich fest, dass dieses Sudoku tatsächlich nicht so schwer ist wie angekündigt (1 Hypothesenebene + 1 Lookahead = 2 Hypothesenebenen). Tatsächlich habe ich noch kein Sudoku gefunden, das mehr als 2 Ebenen von Hypothesen + einen Lookahead (= 3 Ebenen von Hypothesen) erfordert.

Kommentare

• Wie gut ist Ihr Solver gegen sudoku ‚ s mit 17 Einträgen? Z.B. theconversation.com/…
• @SimonStreicher Das Sudoku mit 17 Hinweisen, das Sie zitieren ist schwer, aber nicht zu den härtesten Sudokus im Kontext meines Algorithmus. Im Allgemeinen gibt es keine Korrelation zwischen der Anzahl der Hinweise und der Härte eines Sudoku. Ich habe einige Statistiken über den von mir analysierten Sudokus erstellt.
• @SimonStreicher Ich habe analysierte die Liste der Top 95 Sudokus (nämlich die 95 Hard Puzzles ). Es gibt 5 Sudukos mit Stufe hart (2 Stufen von Hypothesen sind erforderlich), die immer noch 2 Stufen unter der 101 härtesten Sudokus I liegen gefunden haben.
• Vielen Dank für die Info, ich ‚ versuche immer noch, dies alles zu verstehen, zum Glück ist Ihre Website ziemlich gründlich.
• @SimonStreicher Im Kern geht es darum, den Suchraum von der Aktivierung einzelner Werte auf leicht erkennbare Muster (Paare) zu reduzieren, die verwendet werden, um binäre Entscheidungen mit erhöhter Eliminierung von zu generieren Möglichkeiten. Z.B.Zelle1 erlaubt 2 mögliche Werte v1 und v2, Zelle2 erlaubt die gleichen möglichen Werte, aber zusätzlich eine oder mehrere andere Möglichkeiten v3, v4, v5. Daher sind Zelle1 und Zelle2 entweder ein Paar (beide enthalten v1 und v2) oder Zelle 2 kann nur eines von v3, v4, v5 sein. Diese Hypothese wird dann überprüft.

Für dieses Rätsel gibt es nur eine Lösung: Es funktionieren keine bekannten Muster, außer einem etwas intelligenteren Erraten und Überprüfen. Die Anzahl der Schritte, die man vorausschauen muss, um Hinweise zu reduzieren, ist hier die Metrik, und dieses Puzzle benötigt neun aufeinanderfolgende Vermutungen, um einen lösbaren Zustand zu erreichen.

Der Löser in SudokuWiki kann es nicht bekommen, weil es in Javascript einfach zu lange dauern würde und nicht darauf programmiert ist, Zahlen zu erraten.

Die Lösung erfordert, dass man die Werte von Quadraten annimmt und dann das Rätsel reduziert, um zu sehen, ob Sie mehr Annahmen benötigen – wenn Sie dies tun, machen Sie eine andere und fahren Sie fort. Es ist im Wesentlichen eine gründliche Suche nach möglichen Lösungen. Der Löser für sudoku-solutions hat zwar die Lösung für dieses Rätsel gefunden, erklärt jedoch, wenn er aufgefordert wird, die Schritte anzugeben:

Dieser Löser konnte das Rätsel nicht vollständig logisch lösen. Dies bedeutet nicht, dass es keine logische Lösung gibt.

listet dann keine der Schritte auf, mit denen es gelöst wurde. Dies ist nur dann der Fall, wenn der Löser Brute-Force-Verzweigungsschätzungen verwenden muss, um die Lösung zu finden.

Daher kann ich selbst seitdem keine vernünftige Antwort auf die Frage geben, wie dieses Rätsel gelöst werden kann Dazu müsste man diese spezifischen Ketten finden und erklären, warum die andere große Anzahl von Ketten nicht funktioniert.

Aber so machen Sie es: Nehmen Sie an, ein Quadrat ist eine Zahl, dann eine andere, dann eine andere, und überprüfen Sie so lange, bis Sie zu einer Sequenz gekommen sind, die immer noch Sinn macht und es Ihnen ermöglicht, das Rätsel zu lösen, oder Sie sind zu einem Widerspruch gekommen und müssen eine Sicherungskopie erstellen und es erneut versuchen. Ich fürchte, ich denke, dies ist die beste Antwort, die Sie auf diese Frage erhalten können.

Da Sie jedoch nach einer Lösung für das Rätsel gefragt haben, kann ich diese bereitstellen (Mouseover über den Spoilerblock):

Kommentare

• Gute alte Rekursion.
• Ich habe es geschafft, sie mit einer Rekursionstiefe von höchstens 2 Vermutungen zu lösen. Die Naked Singles “ wurde insgesamt 61812 Mal ausgeführt (nach etwas Caching auf einer höheren Ebene, ohne dass die Anzahl der Läufe in Millionen liegt) “ Versteckte Singles “ Strategie 32892 Mal (plus weitere 28920, die aus einem Cache bedient wurden) und eine Suche mit nur 1 Tiefe wurde 256 ausgeführt Mal und weitere 15 Mal aus dem Cache bereitgestellt (an jedem Punkt wurde nur eine Vermutung durchgeführt, obwohl ich glaube, dass die meisten dieser Läufe tatsächlich innerhalb des nächsten stattfanden) und die zweistufige Suche (bei der Sie ‚ 2 Vermutungen anstellen) wurde nur einmal ausgeführt und bekam sie.
• (auch dies ist das einzige Rätsel, das dies nicht tat ‚ knacke nicht mit meinem Programm mit nur EINER Vermutungsstufe)

Nur um eine weitere computerbasierte Lösung hinzuzufügen, verwenden Sie die MiniZinc-Modellierungssprache Sie können das folgende Programm schreiben:

int: n; array[1..n, 1..n] of 0..n: initial_grid; int: reg; array[1..n, 1..n] of 1..reg: regions; array[1..n, 1..n] of var 1..n: final_grid; include "alldifferent.mzn"; constraint forall(r, c in 1..n)(initial_grid[r, c] = 0 \/ initial_grid[r, c] = final_grid[r, c]); constraint forall(r in 1..n)(alldifferent([ final_grid[r, c] | c in 1..n ])); constraint forall(c in 1..n)(alldifferent([ final_grid[r, c] | r in 1..n ])); constraint forall(region in 1..reg)(alldifferent([ final_grid[r, c] | r, c in 1..n where regions[r, c] = region ])); solve satisfy; output [ show_int(1, final_grid[r, c]) ++ if c = n then ("\n" ++ if (r mod 3 = 0 /\ r < n) then "---------------------\n" else "" endif ) elseif c mod 3 = 0 then " | " else " " endif | r, c in 1..n ]; 

Zusammen mit den entsprechenden Daten Datei:

n = 9; reg = 9; regions = array2d(1..9, 1..9, [ 3 * (row div 3) + col div 3 + 1 | row, col in 0..8 ]); initial_grid = [| 8, 0, 0, 0, 0, 0, 0, 0, 0, | 0, 0, 3, 6, 0, 0, 0, 0, 0, | 0, 7, 0, 0, 9, 0, 2, 0, 0, | 0, 5, 0, 0, 0, 7, 0, 0, 0, | 0, 0, 0, 0, 4, 5, 7, 0, 0, | 0, 0, 0, 1, 0, 0, 0, 3, 0, | 0, 0, 1, 0, 0, 0, 0, 6, 8, | 0, 0, 8, 5, 0, 0, 0, 1, 0, | 0, 9, 0, 0, 0, 0, 4, 0, 0 |] ; 

Und mit dem Standardlöser auf einem ziemlich normalen Laptop wird die Lösung in 100 ms veröffentlicht, was die C ++ – Implementierung von PM Lee um ein Vielfaches übertrifft Rand.

Kommentare

• Basiert dieser Algorithmus auf linearer Programmierung?
• Es ‚ s im selben Bereich – Der Solver ist ein Constraint-Programmier-Solver, der gut funktioniert, da das Problem nicht wirklich linear ist, sondern eine Reihe von Constraints verwendet. Er verwendet a. ‚ Kombination von Heuristiken, um den Raum möglicher Lösungen mit einigen ziemlich einfachen Suchmethoden zu reduzieren.
• Ich ‚ bin beeindruckt. Mein Handbuch, sehr einfach lver in Kotlin schlägt es in ungefähr 5 Sekunden auf meinem Laptop mit einer Suchtiefe von maximal 2.