Hvordan løser jeg verdens ' s hårdeste sudoku?

Gæt enkeltværdier i en dybde-første søgning er suboptimal.

Så her er en ræsonnementskæde baseret på en første hypotese / ubeskyttet metode (som min stedsøn modvilligt kalder “veluddannet gætte”).

Bare at følge kæden inklusive modsigelser kræver for at løse 23 varianter af sudoku, så det bruges bedst med en computerstøttet løser. Det kræver dog ingen fancy algoritmer for at følge det. (Jeg bruger mit eget hjemmelavede uoptimerede pythonprogram, så der er ingen reel computing kraft involveret enten).

Notationen følger regnearkkonventioner (kolonne = bogstav, række = antal) (eller skak, hvis du vil).

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 

Jeg har sat skærmbilleder af trinene og en hurtig forklaring af metoden på Verdens hårdeste Sudoku . Da jeg kun er interesseret i at løse hårde gåder ved “uddannet gætte”, fandt jeg ud af, at denne sudoku faktisk ikke er så hård som annonceret (1 hypoteseniveau + 1 lookahead = 2 niveauer af hypoteser). Faktisk har jeg endnu ikke fundet en sudoku, der kræver mere end 2 niveauer af hypoteser + en lookahead (= 3 niveauer af hypoteser).

Kommentarer

• Hvor godt er din solver fair med sudoku ‘ s med 17 poster? For eksempel. theconversation.com/…
• @SimonStreicher Den 17-ledige sudoku, du citerer er hårdt, men ikke blandt de sværeste sudokus i forbindelse med min algoritme. Generelt er der ingen sammenhæng mellem antallet af ledetråde og hårdheden af en sudoku. Jeg har lagt nogle statistikker om de sudokus, jeg har analyseret.
• @SimonStreicher Jeg har analyserede listen over top 95 sudokus (nemlig 95 hårde gåder ). Der er 5 sudukoer med niveau hårdt (2 niveauer af hypoteser er nødvendige), hvilket stadig er 2 niveauer under 101 sværeste sudokus I har fundet.
• Tak for informationen, jeg ‘ Jeg prøver stadig at få mening i det hele, heldigvis er dit websted ret grundigt.
• @SimonStreicher Kernen i det handler om at reducere søgerummet fra at aktivere enkeltværdier til let genkendelige mønstre (par), der bruges til at generere binære beslutninger med øget eliminering af muligheder. For eksempel.cell1 giver mulighed for 2 mulige værdier v1 og v2, cell2 giver mulighed for de samme mulige værdier, men derudover en eller flere andre muligheder v3, v4, v5. Derfor er celle1 og celle2 enten et par (begge indeholder v1 og v2), eller celle 2 kan kun være en af v3, v4, v5. Denne hypotese kontrolleres derefter.

For dette puslespil, mens det har en og kun en løsning, ingen kendte mønstre fungerer på det, bortset fra et lidt mere intelligent gæt-og-check. Antallet af trin, man skal se fremad for at reducere væk spor, er metricen her, og dette puslespil har brug for ni sekventielle gæt for at nå en løselig tilstand.

Løseren på SudokuWiki kan ikke få det, fordi det simpelthen tager for lang tid at gøre det i Javascript, og det er ikke programmeret til at gætte tal.

Løsningen kræver, at man antager værdierne for kvadrater og derefter reducerer puslespillet for at se, om du har brug for flere antagelser – hvis du gør det, lav en anden og fortsæt. Det er en dybde-første-søgning af de mulige løsninger, i det væsentlige. Løseren på sudoku-løsninger kommer med løsningen på dette puslespil, men når han bliver bedt om at give trinene, erklærer han:

Denne løser kunne ikke løse puslespillet helt ved logik, dette betyder ikke, at der ikke er en logisk løsning.

og viser derefter straks ikke nogen af de trin, den brugte til at løse det. Dette sker kun, når opløseren skal bruge brute-force forgrening gætte for at finde løsningen.

Som et resultat er der ingen måde, jeg selv med rimelighed kunne give et “hvordan man løser dette puslespil” svar, da jeg gjorde det ville indebære at finde disse specifikke kæder og forklare, hvorfor den anden store mængde kæder ikke fungerer.

Men sådan gør du det: antag, at et kvadrat er et tal, så et andet, så et andet, og fortsæt med at tjekke, indtil du “er kommet til en sekvens, der stadig giver mening og giver dig mulighed for at løse gåden, eller hvis du er kommet til en modsigelse og har brug for at tage backup og prøve igen. Jeg er bange for, at jeg synes, det er det bedste svar, du kan få på dette spørgsmål.

Da du bede om en løsning på puslespillet, kan jeg dog give det (musen over spoilerblokken):

Kommentarer

• God gammel rekursion.
• Det lykkedes mig at løse det med højst 2 gætter i rekursionsdybde. ” Nøgne singler ” strategi løb i alt 61812 gange (efter noget caching udført på et højere niveau uden at løbstallet er i millioner), ” Skjulte singler ” strategi 32892 gange (plus yderligere 28920, der blev serveret fra en cache) og en søgning med kun dybde 1 blev kørt 256 gange og serveret fra cache 15 gange yderligere (på hvert tidspunkt blev der kun gjort et gæt, selvom jeg tror, de fleste af disse kørsler faktisk skete inden for den næste), og søgningen på to niveauer (hvor du ‘ d gjorde 2 gætter) kun løb en gang og fik det.
• (også dette er det eneste puslespil, der ikke ‘ t knæk med mit program med kun ET niveau af gætte)

Download Singapores premierministers Sudoku-løsning , og giv det dette puslespil (KUN hvis du virkelig sidder fast). Tro det eller ej, at premierministeren lavede et ret robust program, og selv om det ser ud til at sidde fast et stykke tid der, kommer det til sidst ud med følgende 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

Tilsyneladende er det dog muligt at løse med logik ifølge den fyr, der opfandt dette puslespil. Det tog bare opløserne 24 timer at gøre det.

Bemærk: Dette puslespil har 1 på 7. linje i en anden position som spørgsmålet “s. Dette puslespil har flere løsninger.

Kommentarer

• Jeg tvivler på, at dette originale puslespil har flere løsninger (hvis det er det, der er underforstået). Dit input til PM ‘ s løser er sandsynligvis forkert: række 3, kolonne 7 er angivet som input som ” 1 “, ikke ” 7 ” (en af bemærkningerne). Givet det korrekte input til exe, udsender den den kendte løsning.
• @SimonStreicher den forkerte input er i række 7 kolonne 3, hvor 7 skal være en 1
• Sidder den fast i mere end 5 sekunder? Min meget enkle løser formår at få det ind omkring det tid.

Bare for at tilføje en anden computerbaseret løsning og derefter bruge MiniZinc-modelleringssprog , kan du skrive følgende 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 ]; 

Sammen med de relevante 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 |] ; 

Og ved hjælp af standardløseren på en ret standard bærbar computer kommer løsningen i 100 ms, hvilket ikke slår PM Lees C ++ implementering med en betydelig margin.

Kommentarer

• Er denne algoritme baseret på lineær programmering?
• Den ‘ s i samme område – løseren er en begrænsningsprogrammeringsløser, som fungerer godt, da problemet ikke er ‘ t virkelig lineært, men det er en masse begrænsninger. Det bruger en kombination af heuristikker for at reducere pladsen til mulige løsninger med nogle ret grundlæggende søgemetoder.
• Jeg ‘ er imponeret. Min manual, meget enkel så elsker i Kotlin slår det på cirka 5 sekunder på min bærbare computer ved hjælp af en søgedybde på maksimalt 2.