Comment résoudre le sudoku le plus difficile du monde '?

Deviner des valeurs uniques dans une recherche approfondie est sous-optimal.

Voici donc une chaîne de raisonnement basée sur une méthode d’hypothèse / de déformation (que mon beau-fils appelle à contrecœur « deviner éclairé »).

Le simple fait de suivre la chaîne, y compris les contradictions, nécessite pour résoudre 23 variantes du sudoku, il est donc préférable de lutiliser avec un solveur assisté par ordinateur. Cependant, il ne nécessite aucun algorithme sophistiqué pour le suivre. (Jutilise mon propre programme python non optimisé, donc il ny a pas de véritable informatique puissance impliquée soit).

La notation suit les conventions du tableur (colonne = lettre, ligne = numéro) (ou échecs si vous voulez).

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 

Jai mis en place des captures décran des étapes et une explication rapide de la méthode au Le Sudoku le plus dur du monde . Comme je ne suis intéressé que par la résolution dénigmes difficiles par «devinettes éclairées», jai trouvé que ce sudoku nest en fait pas aussi difficile que prévu (1 niveau dhypothèse + 1 anticipation = 2 niveaux dhypothèses). En fait, je nai pas encore trouvé de sudoku qui nécessite plus de 2 niveaux dhypothèses + une anticipation (= 3 niveaux dhypothèses).

Commentaires

• Dans quelle mesure votre solveur est-il juste contre les sudoku ‘ avec 17 entrées? Par exemple. theconversation.com/…
• @SimonStreicher Le sudoku aux 17 indices que vous citez est difficile, mais pas parmi les sudokus les plus difficiles dans le contexte de mon algorithme. Généralement, il ny a pas de corrélation entre le nombre dindices et la dureté dun sudoku. Jai mis en place quelques statistiques sur les sudokus que jai analysés.
• @SimonStreicher Jai a analysé la liste des 95 meilleurs sudokus (à savoir les 95 puzzles difficiles ). Il y a 5 sudukos de niveau hard (2 niveaux dhypothèses sont nécessaires), qui est toujours 2 niveaux en dessous des 101 sudokus les plus durs I
• Merci pour linfo, ‘ jessaie toujours de comprendre tout cela, heureusement votre site Web est assez complet.
• @SimonStreicher Le cœur de celui-ci consiste à réduire lespace de recherche de lactivation de valeurs uniques à des modèles (paires) facilement reconnaissables qui sont utilisés pour générer des décisions binaires avec une élimination accrue de possibilités. Par exemple.cell1 permet 2 valeurs possibles v1 et v2, cell2 permet les mêmes valeurs possibles, mais en plus une ou plusieurs autres possibilités v3, v4, v5. Par conséquent, cellule1 et cellule2 sont soit une paire (les deux contiennent v1 et v2), soit la cellule 2 ne peut être que lune des v3, v4, v5. Cette hypothèse est ensuite vérifiée.

Pour ce puzzle, alors quil na quune et une seule solution, aucun modèle connu ne fonctionne dessus, à part une estimation et une vérification légèrement plus intelligente. Le nombre détapes à suivre pour réduire les indices est la métrique ici, et ce puzzle a besoin de neuf suppositions séquentielles pour atteindre un état résoluble.

Le solveur sur SudokuWiki ne peut pas lobtenir parce que cela prendrait trop de temps à faire en Javascript, et il nest pas programmé pour deviner les nombres.

La solution nécessite que lon assume les valeurs des carrés, puis réduise le puzzle pour voir si vous avez besoin de plus dhypothèses – si vous le faites, faites-en une autre et continuez. Il sagit essentiellement dune recherche approfondie des solutions possibles. Le solveur sur sudoku-solutions propose la solution à ce casse-tête, mais lorsquon lui demande de fournir les étapes, déclare:

Ce solveur na pas pu résoudre le puzzle complètement par la logique, cela ne signifie pas quil ny a pas de solution logique.

et échoue rapidement à répertorier aucune des étapes utilisées pour le résoudre. Cela ne se produit que lorsque le solveur doit utiliser des devinettes de branchement par force brute pour trouver la solution.

En conséquence, il ny a aucun moyen pour moi de fournir une réponse « comment résoudre ce casse-tête », depuis cela impliquerait de trouver ces chaînes spécifiques et dexpliquer pourquoi lautre grande quantité de chaînes ne fonctionne pas.

Mais cest ainsi que vous procédez: supposons quun carré est un nombre, puis un autre, puis un autre, et continuez à vérifier jusquà ce que vous arriviez à une séquence qui a encore du sens et vous permette de résoudre le puzzle, ou que vous soyez arrivé à une contradiction et que vous ayez besoin de reculer et de réessayer. Jai bien peur de penser que cest la meilleure réponse que vous puissiez obtenir à cette question.

Puisque vous avez demandé une solution au casse-tête, cependant, je peux la fournir (passez la souris sur le bloc spoiler):

Commentaires

• Bonne vieille récursivité.
• Jai réussi à le résoudre avec une profondeur de récursivité de 2 suppositions au maximum. Le Naked Singles  » a été exécutée un total de 61812 fois (après une mise en cache effectuée à un niveau supérieur, sans que le nombre dexécutions soit en millions), le  » Singles cachés  » stratégie 32892 fois (plus 28920 autres qui ont été servis à partir dun cache) et une recherche avec une profondeur seulement 1 a été exécutée 256 fois et servi à partir du cache 15 fois (à chaque point, une seule estimation a été faite, bien que je pense que la plupart de ces exécutions se sont réellement déroulées dans la suivante), et la recherche à deux niveaux (où vous ‘ faites 2 suppositions) na été lancée quune seule fois et la obtenue.
• (cest aussi le seul casse-tête qui na ‘ t craquer avec mon programme avec un seul niveau de devinettes)

Téléchargez le solveur Sudoku du premier ministre de Singapour et alimentez-le avec ce puzzle (UNIQUEMENT si vous « êtes VRAIMENT coincé). Croyez-le ou non, ce premier ministre a élaboré un programme assez robuste, et même sil semble y rester bloqué pendant un certain temps, il aboutit finalement à la solution suivante:

862 || 751 || 349
943 || 628 || 157
571 || 493 || 286
============
159 || 387 || 624
386 || 245 || 791
724 || 169 || 835
============
217 || 934 || 568
438 || 576 || 912
695 || 812 || 473

Apparemment, il est possible de résoudre avec la logique, cependant, selon le type qui a inventé ce puzzle. Il a juste fallu 24 heures aux solveurs pour le faire.

Remarque: ce puzzle a le 1 sur la 7ème ligne dans une position différente en tant que question. Ce puzzle a plusieurs solutions.

Commentaires

• Je doute que ce puzzle original ait plusieurs solutions (si cela est sous-entendu). Votre contribution au PM ‘ s solveur est probablement erroné: ligne 3, colonne 7 est donnée en entrée comme  » 1 « , pas  » 7  » (lune des observations). Étant donné lentrée correcte dans lexe, il renvoie la solution connue.
• @SimonStreicher la mauvaise entrée est à la ligne 7, colonne 3 où le 7 devrait être un 1
• Est-ce quil reste bloqué pendant plus de 5 secondes? Mon solveur très simple parvient à le comprendre quantité de temps.

Juste pour ajouter une autre solution informatique, puis en utilisant le langage de modélisation MiniZinc , vous pouvez écrire le programme suivant:

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 ]; 

avec les données appropriées file:

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 |] ; 

Et en utilisant le solveur par défaut sur un ordinateur portable assez standard, la solution sort en 100 ms, ce qui bat considérablement limplémentation C ++ de PM Lee. margin.

Commentaires

• Cet algorithme est-il basé sur la programmation linéaire?
• Il ‘ s dans le même domaine – le solveur est un solveur de programmation de contraintes, qui fonctionne bien puisque le problème nest ‘ t vraiment linéaire mais cest un tas de contraintes. Il utilise un combinaison dheuristiques pour réduire lespace des solutions possibles avec des méthodes de recherche assez basiques.
• Je ‘ suis impressionné. Mon manuel, très simple donc lver à Kotlin le bat en environ 5 secondes sur mon ordinateur portable, en utilisant une profondeur de recherche de maximum 2.