Cum rezolv cel mai greu sudoku din lume '?

Ghicirea valorilor individuale într-o căutare în profunzime este sub-optim.

Deci, iată un lanț de raționament bazat pe o ipoteză largă / metodă de dezamorsare (pe care fiul meu vitreg îl numește cu reticență „ghicire educată”).

Doar urmărirea lanțului, inclusiv contradicțiile, necesită pentru a rezolva 23 de variante ale sudoku-ului, deci este cel mai bine folosit cu un rezolvator asistat de computer. Cu toate acestea, nu necesită algoritmi fantezi pentru a-l urma. (Folosesc propriul meu program Python neoptimizat cultivat acasă, deci nu există calcule reale puterea implicată fie).

Notarea urmează convențiile foilor de calcul (coloană = literă, rând = număr) (sau șah dacă vreți).

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 

Am realizat capturi de ecran ale pașilor și o explicație rapidă a metodei la Cel mai greu sudoku din lume . Deoarece sunt interesat doar să rezolv puzzle-uri dure prin „ghicire educată”, am constatat că acest sudoku nu este de fapt atât de greu ca cel publicat (1 nivel de ipoteză + 1 lookahead = 2 niveluri de ipoteze). De fapt, nu am găsit încă un sudoku care să necesite mai mult de 2 niveluri de ipoteze + o singură privire (= 3 niveluri de ipoteze).

Comentarii

• Cât de bine este corect rezolvatorul dvs. împotriva sudoku ‘ cu 17 intrări? De exemplu. theconversation.com/…
• @SimonStreicher Sudoku cu 17 indicii, pe care îl citați este greu, dar nu printre cele mai grele sudokus din contextul algoritmului meu. În general, nu există nicio corelație între numărul de indicii și duritatea unui sudoku. Am publicat câteva statistici despre sudokurile pe care le-am analizat.
• @SimonStreicher Am a analizat lista celor mai populare 95 sudokus (și anume 95 Hard Puzzles ). Există 5 suduko-uri cu nivel greu (sunt necesare 2 nivele de ipoteze), care este încă cu 2 niveluri sub 101 sudokusuri cele mai dure I am găsit.
• Vă mulțumim pentru informații, încă ‘ încerc să dau sens tuturor, din fericire, site-ul dvs. web este destul de detaliat.
• @SimonStreicher Nucleul acesteia este despre reducerea spațiului de căutare de la activarea valorilor unice la modele ușor de recunoscut (perechi) care sunt folosite pentru a genera decizii binare cu eliminarea crescută a posibilități. De exemplu.celula1 permite 2 valori posibile v1 și v2, celula2 permite aceleași valori posibile, dar în plus una sau mai multe alte posibilități v3, v4, v5. Prin urmare, celula1 și celula2 sunt fie o pereche (ambele conțin v1 și v2), fie celula 2 poate fi doar una dintre v3, v4, v5. Această ipoteză este apoi verificată.

Pentru acest puzzle, în timp ce are o singură soluție, nu funcționează niciun model cunoscut, în afară de o ghicire și verificare puțin mai inteligentă. Numărul de pași pe care trebuie să-i urmăriți pentru a reduce indiciile este metrica de aici, iar acest puzzle are nevoie de nouă presupuneri secvențiale pentru a ajunge la o stare rezolvabilă.

Solverul din SudokuWiki nu îl poate obține, deoarece pur și simplu ar dura prea mult timp în Javascript și nu este programat să ghicească numerele.

Soluția necesită asumarea valorilor pătratelor și apoi reducerea puzzle-ului pentru a vedea dacă aveți nevoie de mai multe ipoteze – dacă da, faceți alta și continuați. În esență, este o căutare profundă a soluțiilor posibile. Solverul din sudoku-solutions vine cu soluția acestui puzzle, dar când i se cere să furnizeze pașii, declară:

Acest rezolvator nu a putut rezolva complet puzzle-ul prin logică, acest lucru nu înseamnă că nu există o soluție logică.

și apoi nu reușește să listeze oricare dintre pașii pe care i-a folosit pentru a-l rezolva. Acest lucru se întâmplă numai atunci când rezolvatorul trebuie să folosească ghicitul de ramificare cu forță brută pentru a găsi soluția.

Prin urmare, nu există nicio modalitate prin care eu însumi aș putea oferi în mod rezonabil un răspuns „cum să rezolv acest puzzle”, deci ar implica găsirea acestor lanțuri specifice și explicarea de ce cealaltă mare cantitate de lanțuri nu funcționează.

Dar așa procedați: presupunem că un pătrat este un număr, apoi altul, apoi altul, și continuați să verificați până când veți ajunge la o secvență care încă are sens și vă permite să rezolvați puzzle-ul sau când ați ajuns la o contradicție și trebuie să faceți backup și să încercați din nou. Mă tem că cred că acesta este cel mai bun răspuns pe care îl puteți obține la această întrebare.

Deoarece ați cerut o soluție la puzzle, totuși, o pot oferi (trecând mouse-ul peste blocul spoiler):

Comentarii

• Recursivitate veche bună.
• Am reușit să o rezolv cu o adâncime de recursiune de cel mult 2 presupuneri. Naked Singles ” a rulat un total de 61812 ori (după unele cache-uri efectuate la un nivel superior, fără ca numărul de rulări să fie în milioane), ” Hidden Singles ” strategie de 32892 ori (plus încă 28920 care au fost servite dintr-o memorie cache) și o căutare cu adâncimea de numai 1 a fost executată 256 ori și a fost difuzat din cache de încă 15 ori (în fiecare moment s-a făcut o singură presupunere, deși cred că majoritatea acestor rulări s-au întâmplat de fapt în următoarea), iar căutarea pe două niveluri (unde ‘ ați făcut 2 presupuneri) a rulat o singură dată și a obținut-o.
• (de asemenea, acesta este singurul puzzle care nu a făcut ‘ t crack cu programul meu cu un singur nivel de ghicire)

Descărcați rezolvatorul Sudoku din Singapore și alimentați-l cu acest puzzle (NUMAI dacă sunteți cu adevărat blocat). Credeți sau nu, prim-ministrul a făcut un program destul de robust și, deși se pare că s-a blocat o vreme acolo, în cele din urmă iese cu următoarea soluție:

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

Aparent, totuși, este posibil să se rezolve cu logică, conform tipului care a inventat acest puzzle. Rezolvatorii au durat 24 de ore pentru a o face.

Notă: acest puzzle are 1 pe linia a 7-a într-o poziție diferită ca întrebarea „s. Acest puzzle are mai multe soluții.

Comentarii

• Mă îndoiesc că acest puzzle original are mai multe soluții (dacă este ceea ce este implicit). Contribuția dvs. la PM ‘ este probabil greșit: rândul 3, coloana 7 este dată ca intrare ca ” 1 „, not ” 7 ” (unul din observații). Având în vedere intrarea corectă în exe, scoate soluția cunoscută.
• @SimonStreicher intrarea greșită este la rândul 7 coloana 3 unde 7 ar trebui să fie un 1
• Se blochează mai mult de 5 secunde? Solverul meu foarte simplu reușește să o facă în legătură cu asta cantitatea de timp.

Doar pentru a adăuga o altă soluție computerizată, apoi folosind Limbajul de modelare MiniZinc puteți scrie următorul program:

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

Împreună cu datele corespunzătoare fișier:

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

Și folosind soluția implicită pe un laptop destul de standard, soluția iese în 100 ms, ceea ce depășește implementarea C ++ a PM Lee cu o creștere considerabilă margin.

Comentarii

• Este acest algoritm bazat pe programare liniară?
• Este ‘ s în același tărâm – solverul este un rezolvator de programare a constrângerilor, care funcționează bine, deoarece problema nu este ‘ t într-adevăr liniară, dar este o grămadă de constrângeri. combinație de euristică pentru a reduce spațiul posibilelor soluții cu câteva metode de căutare destul de elementare.
• Am ‘ m impresionat. Manualul meu, foarte simplu, așa că Lver din Kotlin îl bate în aproximativ 5 secunde pe laptopul meu, folosind o adâncime de căutare de maxim 2.