Come risolvo il sudoku più difficile del mondo '?

Indovinare singoli valori in una ricerca approfondita non è ottimale.

Quindi, ecco una catena di ragionamento basata su un metodo di ipotesi / confutazione ampia (che il mio figliastro chiama a malincuore “supposizione istruita”).

Basta seguire la catena che include le contraddizioni per risolvere 23 varianti del sudoku, quindi è meglio usarlo con un risolutore assistito da computer. Tuttavia, non richiede algoritmi elaborati per seguirlo. (Io uso il mio programma Python non ottimizzato di mia produzione, quindi non esiste un vero computer potenza coinvolta sia).

La notazione segue le convenzioni del foglio di calcolo (colonna = lettera, riga = numero) (o scacchi se vuoi).

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 

Ho messo delle schermate dei passaggi e una rapida spiegazione del metodo in World “s Hardest Sudoku . Dal momento che mi interessa solo risolvere enigmi difficili da “indovinare istruito”, ho scoperto che questo sudoku in realtà non è così difficile come pubblicizzato (1 livello di ipotesi + 1 lookahead = 2 livelli di ipotesi). Infatti, non ho ancora trovato un sudoku che richieda più di 2 livelli di ipotesi + un lookahead (= 3 livelli di ipotesi).

Commenti

• In che misura il tuo risolutore è equo contro i sudoku ‘ con 17 voci? Per esempio. theconversation.com/…
• @SimonStreicher The 17-clue sudoku, stai citando è difficile, ma non tra i sudoku più difficili nel contesto del mio algoritmo. In generale, non cè correlazione tra il numero di indizi e la durezza di un sudoku. Ho pubblicato alcune statistiche sui sudoku che ho analizzato.
• @SimonStreicher Ho ha analizzato lelenco dei 95 migliori sudoku (vale a dire i 95 puzzle difficili ). Ci sono 5 sudukos con livello hard (sono necessari 2 livelli di ipotesi), che è ancora 2 livelli al di sotto dei 101 sudoku più difficili I hanno trovato.
• Grazie per le informazioni, ‘ sto ancora cercando di dare un senso a tutto questo, fortunatamente il tuo sito web è abbastanza completo.
• @SimonStreicher Il fulcro è di ridurre lo spazio di ricerca dallattivazione di valori singoli a modelli (coppie) facilmente riconoscibili che vengono utilizzati per generare decisioni binarie con una maggiore eliminazione di possibilità. Per esempio.cell1 consente 2 valori possibili v1 e v2, cell2 consente gli stessi valori possibili, ma in aggiunta una o più altre possibilità v3, v4, v5. Pertanto, cella1 e cella2 sono una coppia (entrambe contengono v1 e v2) oppure la cella 2 può essere solo una di v3, v4, v5. Questa ipotesi viene quindi verificata.

Per questo puzzle, sebbene abbia una e una sola soluzione, nessuno schema noto funziona su di esso, a parte una supposizione e verifica leggermente più intelligente. Il numero di passaggi che uno deve guardare avanti per ridurre gli indizi è la metrica qui, e questo puzzle richiede nove tentativi sequenziali per raggiungere uno stato risolvibile.

Il risolutore su SudokuWiki non può ottenerlo perché semplicemente impiegherebbe troppo tempo per farlo in Javascript e non è programmato per indovinare i numeri.

La soluzione richiede che uno assuma i valori dei quadrati, e poi riduca il puzzle per vedere se hai bisogno di più ipotesi – se lo fai, creane un altro e continua. Si tratta, in sostanza, di una ricerca approfondita delle possibili soluzioni. Il risolutore di sudoku-solutions ha trovato la soluzione a questo puzzle, ma quando gli viene chiesto di fornire i passaggi, dichiara:

Questo risolutore non è stato in grado di risolvere completamente il puzzle con la logica, questo non significa che non ci sia una soluzione logica.

e poi prontamente non riesce a elencare nessuno dei passaggi utilizzati per risolverlo. Questo accade solo quando il risolutore deve usare la forza bruta per indovinare le ramificazioni per trovare la soluzione.

Di conseguenza, io stesso non potrei ragionevolmente fornire una risposta “come risolvere questo enigma”, dal momento che ho fatto quindi comporterebbe la ricerca di queste catene specifiche e la spiegazione del motivo per cui laltra grande quantità di catene non funziona.

Ma è così che lo fai: supponi che un quadrato sia un numero, poi un altro, poi un altro, e continua a controllare finché non sei arrivato a una sequenza che ha ancora senso e ti consente di risolvere il puzzle, o sei arrivato a una contraddizione e hai bisogno di tornare indietro e riprovare. Temo che questa sia la risposta migliore che puoi ottenere a questa domanda.

Dato che hai chiesto una soluzione al puzzle, tuttavia, posso fornirla (passaggio del mouse sopra il blocco spoiler):

Commenti

• Buona vecchia ricorsione.
• Sono riuscito a risolverlo con una profondità di ricorsione di 2 ipotesi al massimo. Il ” Naked Singles ” è stata eseguita in totale 61812 volte (dopo un po di memorizzazione nella cache a un livello superiore, senza che il conteggio delle esecuzioni sia di milioni) ” Hidden Singles ” strategia 32892 volte (più altre 28920 fornite da una cache) e una ricerca con profondità solo 1 è stata eseguita 256 volte e servito dalla cache altre 15 volte (ad ogni punto è stata fatta una sola ipotesi, anche se credo che la maggior parte di queste esecuzioni siano effettivamente avvenute entro quella successiva), e la ricerca a due livelli (dove ‘ hai fatto 2 tentativi) è stata eseguita solo una volta e lha ottenuta.
• (anche questo è lunico puzzle che non ‘ t crack con il mio programma con UN SOLO livello di indovinare)

Scarica il risolutore di Sudoku del primo ministro di Singapore e inserisci questo puzzle (SOLO se sei VERAMENTE bloccato). Che tu ci creda o no, quel primo ministro ha realizzato un programma piuttosto robusto e, anche se sembra che rimanga bloccato per un po , alla fine esce con la seguente soluzione:

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

A quanto pare è possibile risolvere con la logica, comunque, secondo il ragazzo che ha inventato questo puzzle. I risolutori hanno impiegato 24 ore per farlo.

Nota: questo puzzle ha l1 sulla settima riga in una posizione diversa rispetto alla domanda “. Questo puzzle ha più soluzioni.

Commenti

• Dubito che questo puzzle originale abbia più soluzioni (se questo è ciò che è implicito). Il tuo contributo al PM ‘ è probabilmente sbagliato: la riga 3, la colonna 7 è fornita come input come ” 1 “, non ” 7 ” (una delle osservazioni). Dato linput corretto allexe, restituisce la soluzione nota.
• @SimonStreicher linput sbagliato è alla riga 7 colonna 3 dove il 7 dovrebbe essere un 1
• Si blocca per più di 5 secondi? Il mio semplicissimo risolutore riesce a capirlo quantità di tempo.

Solo per aggiungere unaltra soluzione basata su computer, quindi utilizzare Linguaggio di modellazione MiniZinc puoi scrivere il seguente programma:

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

Insieme ai dati appropriati 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 |] ; 

E usando il risolutore predefinito su un laptop abbastanza standard la soluzione esce in 100 ms, il che batte limplementazione C ++ di PM Lee di un considerevole margin.

Commenti

• Questo algoritmo è basato sulla programmazione lineare?
• ‘ s nello stesso ambito: il solutore è un risolutore di programmazione di vincoli, che funziona bene poiché il problema non è ‘ t veramente lineare ma è un insieme di vincoli. Utilizza un combinazione di euristica per ridurre lo spazio delle possibili soluzioni con alcuni metodi di ricerca abbastanza semplici.
• Sono ‘ impressionato. Il mio manuale, molto semplice lver in Kotlin lo batte in circa 5 secondi sul mio laptop, utilizzando una profondità di ricerca massima di 2.