Hur löser jag världens ' hårdaste sudoku?

Gissa enskilda värden i en djup-första sökning är suboptimalt.

Så här är en resonemangskedja baserad på en bredd-första hypotes / otät metod (som min styvson motvilligt kallar ”utbildat gissning”).

Att bara följa kedjan inklusive motsägelser kräver för att lösa 23 varianter av sudoku, så det används bäst med en datorstödd lösare. Det kräver dock inga snygga algoritmer för att följa den. (Jag använder mitt eget odlade ooptimerade pythonprogram, så det finns ingen riktig makt involverad antingen).

Notationen följer kalkylbladskonventioner (kolumn = bokstav, rad = nummer) (eller schack om du vill).

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 

Jag har lagt upp skärmbilder av stegen och en snabb förklaring av metoden på Världens hårdaste Sudoku . Eftersom jag bara är intresserad av att lösa hårda pussel med ”utbildad gissning”, fann jag att denna sudoku faktiskt inte är så svår som annonserad (1 hypotesnivå + 1 lookahead = 2 hypotesnivåer). Jag har faktiskt ännu inte hittat en sudoku som kräver mer än två nivåer av hypoteser + en lookahead (= 3 nivåer av hypoteser).

Kommentarer

• Hur väl är din lösare rättvis mot sudoku ’ med 17 poster? T.ex. theconversation.com/…
• @SimonStreicher Den 17-lediga sudoku, citerar du är svårt, men inte bland de svåraste sudokus i samband med min algoritm. Generellt finns det ingen korrelation mellan antalet ledtrådar och hårdheten hos en sudoku. Jag har lagt upp lite statistik om de sudokus jag har analyserat.
• @SimonStreicher Jag har analyserade listan över topp 95 sudokus (nämligen 95 hårda pussel ). Det finns 5 sudukor med nivå hård (två nivåer av hypoteser är nödvändiga), vilket fortfarande ligger två nivåer under 101 hårdaste sudokus I har hittat.
• Tack för informationen, jag ’ Jag försöker fortfarande förstå allt detta, lyckligtvis är din webbplats ganska grundlig.
• @ SimonStreicher Kärnan i det handlar om att minska sökutrymmet från att aktivera enstaka värden till lätt igenkännbara mönster (par) som används för att generera binära beslut med ökad eliminering av möjligheter. T.ex.cell1 möjliggör två möjliga värden v1 och v2, cell2 möjliggör samma möjliga värden, men dessutom en eller flera andra möjligheter v3, v4, v5. Därför är cell1 och cell2 antingen ett par (båda innehåller v1 och v2) eller cell 2 kan bara vara en av v3, v4, v5. Denna hypotes kontrolleras sedan.

För det här pusslet, medan det har en och en lösning, inga kända mönster fungerar på det, förutom en lite mer intelligent gissning och kontroll. Antalet steg man måste se framåt för att minska bort ledtrådar är mätvärdet här, och detta pussel behöver nio sekventiella gissningar för att nå ett lösbart tillstånd.

Lösaren på SudokuWiki kan inte få det eftersom det helt enkelt skulle ta för lång tid att göra i Javascript, och det är inte programmerat att gissa siffror.

Lösningen kräver att man antar värdena på rutor och sedan minskar pusslet för att se om du behöver fler antaganden – om du gör det, gör ett annat och fortsätt. Det är en djup-första-sökning av möjliga lösningar, i huvudsak. Lösaren på sudoku-lösningar kommer med lösningen på detta pussel, men när han ombeds att tillhandahålla stegen, förklarar:

Den här lösaren kunde inte lösa pusslet helt med logik, detta betyder inte att det inte finns någon logisk lösning.

och misslyckas sedan med att lista någon av de steg den använde för att lösa det. Detta händer bara när lösaren måste använda brute-force grening-gissningar för att hitta lösningen.

Som ett resultat finns det inget sätt jag själv rimligt kunde ge ett ”hur man löser detta pussel” -svar, eftersom jag gjorde så skulle det innebära att hitta dessa specifika kedjor och förklara varför den andra stora mängden kedjor inte fungerar.

Men så gör du det: antar att ett kvadrat är ett tal, sedan ett annat, sedan ett annat, och fortsätt kontrollera tills du har kommit till en sekvens som fortfarande är meningsfull och som låter dig lösa pusslet, eller så har du kommit till en motsägelse och behöver säkerhetskopiera och försöka igen. Jag är rädd att jag tycker att det här är det bästa svaret du kan få på den här frågan.

Eftersom du frågade efter en lösning på pusslet kan jag dock ge den (musen över spoilerblocket): / p>

Kommentarer

• Bra gammal rekursion.
• Jag lyckades lösa det med rekursionsdjup på högst två gissningar. ” Nakna singlar ” -strategin sprang totalt 61812 gånger (efter en viss cachning på en högre nivå, utan att körantalet är i miljoner), ” Dolda singlar ” strategi 32892 gånger (plus ytterligare 28920 som serverades från en cache) och en sökning med endast 1 djup kördes 256 gånger och serveras från cache ytterligare 15 gånger (vid varje punkt gjordes bara en gissning, även om jag tror att de flesta av dessa körningar faktiskt hände inom nästa), och sökningen på två nivåer (där du ’ d gjorde två gissningar) sprang bara en gång och fick den.
• (också detta är det enda pusslet som inte ’ t knäcka med mitt program med bara EN nivå att gissa)

Ladda ned Singapores premiärminister Sudoku-lösare och mata det här pusslet (ENDAST om du verkligen är fast). Tro det eller ej, att premiärministern gjorde ett ganska robust program, och även om det ser ut att det fastnar ett tag där, så kommer det så småningom ut med följande lösning:

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

Tydligen är det dock möjligt att lösa med logik, enligt killen som uppfann detta pussel. Det tog bara lösarna 24 timmar att göra det.

Obs: Detta pussel har 1 på 7: e raden i en annan position som frågan ”s. Detta pussel har flera lösningar.

Kommentarer

• Jag tvivlar på att det här ursprungliga pusslet har flera lösningar (om det är vad som antyds). Din inmatning till PM ’ s lösare är förmodligen fel: rad 3, kolumn 7 ges som inmatning som ” 1 ”, inte ” 7 ” (en av observationerna). Med tanke på den korrekta inmatningen till exe, matar den ut den kända lösningen.
• @SimonStreicher fel inmatning är i rad 7 kolumn 3 där 7 ska vara en 1
• Får den fast i mer än 5 sekunder? Min väldigt enkla lösare lyckas få in den om det tid.

Bara för att lägga till ytterligare en datorbaserad lösning, använd sedan MiniZinc-modelleringsspråk kan du skriva följande 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 ]; 

Tillsammans med lämpliga data 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 |] ; 

Och med standardlösaren på en ganska standard bärbar dator kommer lösningen på 100 ms, vilket slår PM Lees C ++ implementering med en avsevärd marginal.

Kommentarer

• Är denna algoritm baserad på linjär programmering?
• Den ’ s inom samma område – lösaren är en begränsningsprogrammeringslösare, vilket fungerar bra eftersom problemet inte är ’ t riktigt linjärt men det är en massa begränsningar. Den använder en kombination av heuristik för att minska utrymmet av möjliga lösningar med några ganska grundläggande sökmetoder.
• Jag ’ är imponerad. Min manual, mycket enkel så älskaren i Kotlin slår den på cirka 5 sekunder på min bärbara dator med ett sökdjup på maximalt 2.