Hvordan løser jeg verdens ' s vanskeligste sudoku?

Gjette enkeltverdier i et dybde-første søk er suboptimal.

Så her er en resonnementskjede basert på en bredde-første hypotese / ubeskyttet metode (som stesønnen min motvillig kaller «utdannet gjetting»).

Bare å følge kjeden inkludert motsetninger krever for å løse 23 varianter av sudoku, så den brukes best sammen med en datamaskinstøttet løser. Det krever imidlertid ingen fancy algoritmer for å følge den. (Jeg bruker mitt eget hjemmelagde uoptimerte pythonprogram, så det er ingen reell databehandling kraft involvert heller.

Notasjonen følger regnearkkonvensjoner (kolonne = bokstav, rad = nummer) (eller sjakk om 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 satt opp skjermbilder av trinnene og en rask forklaring på metoden på Verdens hardeste Sudoku . Siden jeg bare er interessert i å løse harde gåter med «utdannet gjetting», fant jeg ut at denne sudoku faktisk ikke er så vanskelig som annonsert (1 hypotesenivå + 1 lookahead = 2 nivåer av hypoteser). Faktisk har jeg ennå ikke funnet en sudoku som krever mer enn 2 nivåer av hypoteser + ett blikkhode (= 3 nivåer av hypoteser).

Kommentarer

• Hvor godt er løseren din rettferdig mot sudoku ‘ s med 17 oppføringer? F.eks. theconversation.com/…
• @SimonStreicher 17-leddet sudoku, du siterer er vanskelig, men ikke blant de vanskeligste sudokusene i sammenheng med algoritmen min. Generelt er det ingen sammenheng mellom antall ledetråder og hardheten til en sudoku. Jeg har lagt opp litt statistikk om sudokusene jeg har analysert.
• @SimonStreicher Jeg har analyserte listen over topp 95 sudokus (nemlig 95 Hard Puzzles ). Det er 5 sudukoer med nivå hard (to nivåer av hypoteser er nødvendige), som fortsatt er 2 nivåer under 101 vanskeligste sudokus I har funnet.
• Takk for informasjonen, jeg ‘ Jeg prøver fortsatt å gi mening om dette, heldigvis er nettstedet ditt ganske grundig.
• @SimonStreicher Kjernen i det handler om å redusere søkeområdet fra å aktivere enkeltverdier til lett gjenkjennelige mønstre (par) som brukes til å generere binære beslutninger med økt eliminering av muligheter. F.eks.celle1 tillater to mulige verdier v1 og v2, celle2 tillater de samme mulige verdiene, men i tillegg en eller flere andre muligheter v3, v4, v5. Derfor er celle1 og celle2 enten et par (begge inneholder v1 og v2) eller celle 2 kan bare være en av v3, v4, v5. Denne hypotesen blir deretter sjekket.

For dette puslespillet, mens det har en eneste løsning, ingen kjente mønstre fungerer på det, annet enn en litt mer intelligent gjetning og sjekk. Antall trinn man må se fremover for å redusere bort ledetråder er beregningen her, og dette puslespillet trenger ni sekvensielle gjetninger for å nå en løsbar tilstand.

Løseren på SudokuWiki kan ikke få det fordi det bare tar for lang tid å gjøre det i Javascript, og det er ikke programmert til å gjette tall.

Løsningen krever at man antar kvadratverdiene, og deretter reduserer puslespillet for å se om du trenger flere antagelser – hvis du gjør det, lag en annen og fortsett. Det er en dybde-første-søk av mulige løsninger, i hovedsak. Løseren på sudoku-løsninger kommer opp med løsningen på dette puslespillet, men når han blir bedt om å gi trinnene, erklærer:

Denne løseren kunne ikke løse puslespillet helt med logikk, dette betyr ikke at det ikke er en logisk løsning.

og klarer så ikke å liste noen av trinnene den brukte for å løse det. Dette skjer bare når løseren må bruke brute-kraft forgrening gjetting for å finne løsningen.

Som et resultat er det ingen måte jeg selv med rimelighet kan gi et «hvordan løse dette puslespillet» svar, siden jeg gjorde så ville innebære å finne disse spesifikke kjedene og forklare hvorfor den andre store mengden kjeder ikke fungerer.

Men slik gjør du det: antar at et kvadrat er et tall, så et annet, så et annet, og fortsett å sjekke til du har kommet til en sekvens som fremdeles gir mening og lar deg løse puslespillet, eller du har kommet til en motsetning og trenger å sikkerhetskopiere og prøve igjen. Jeg er redd jeg tror dette er det beste svaret du kan få på dette spørsmålet.

Siden du spurte om en løsning på puslespillet, kan jeg imidlertid gi det (musen over spoilerblokken):

Kommentarer

• God gammel rekursjon.
• Jeg klarte å løse det med rekursjonsdybde på maksimalt 2 gjetninger. » Nakne singler » strategi kjørte totalt 61812 ganger (etter noen caching gjort på et høyere nivå, uten at antall løp er i millioner), » Skjulte singler » strategi 32892 ganger (pluss ytterligere 28920 som ble servert fra en cache) og et søk med bare dybde 1 ble kjørt 256 ganger og servert fra hurtigbufferen ytterligere 15 ganger (på hvert punkt ble bare ett gjetning gjort, selv om jeg tror at de fleste av disse løpene faktisk skjedde i løpet av den neste), og søken på to nivåer (der du ‘ d gjorde 2 gjetninger) bare løp en gang og fikk den.
• (også dette er det eneste puslespillet som ikke ‘ t knekk med programmet mitt med bare ett nivå av gjetting)

Last ned statsminister i Singapores Sudoku-løser og gi den dette puslespillet (KUN hvis du virkelig sitter fast). Tro det eller ei, at statsministeren lagde et ganske robust program, og selv om det ser ut som det sitter fast en stund der, kommer det til slutt ut 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

Det er tilsynelatende mulig å løse med logikk, ifølge fyren som oppfant dette puslespillet. Det tok bare 24 timer å gjøre det.

Merk: Dette puslespillet har 1 på 7. linje i en annen posisjon som spørsmålet «s. Dette puslespillet har flere løsninger.

Kommentarer

• Jeg tviler på at dette originale puslespillet har flere løsninger (hvis det er det som er underforstått). Din innspill til PM ‘ s løser er sannsynligvis feil: rad 3, kolonne 7 er gitt som inngang som » 1 «, ikke » 7 » (en av observasjonene). Gitt riktig inngang til exe, gir den den kjente løsningen.
• @ SimonStreicher feil input er i rad 7 kolonne 3 der 7 skal være en 1
• Sitter den fast i mer enn 5 sekunder? Den veldig enkle løseren min klarer å få den inn omtrent det mengde tid.

Bare for å legge til en annen datamaskinbasert løsning, bruk deretter MiniZinc-modelleringsspråk 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 aktuelle dataene 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 å bruke standardløseren på en ganske standard bærbar PC kommer løsningen på 100 ms, noe som slår PM Lees C ++ implementering med en betydelig margin.

Kommentarer

• Er denne algoritmen basert på lineær programmering?
• Den ‘ s i samme rike – løseren er en begrensningsprogrammeringsløser, som fungerer bra siden problemet ikke er ‘ t veldig lineært, men det er en mengde begrensninger. Det bruker en kombinasjon av heuristikk for å redusere plassen til mulige løsninger med noen ganske grunnleggende søkemetoder.
• Jeg ‘ er imponert. Min manual, veldig enkel så elsker i Kotlin slår den på omtrent 5 sekunder på den bærbare datamaskinen min, med en søkedybde på maksimalt 2.