Hoe los ik de ' s moeilijkste sudoku van de wereld op?

Enkele waarden raden bij een eerste zoekactie is niet optimaal.

Dus, hier is een redeneringsketen die is gebaseerd op een breedte-eerst hypothese / weerleggingsmethode (die mijn stiefzoon met tegenzin opgeleid gissen noemt).

Het volgen van de ketting, inclusief tegenstrijdigheden, vereist om 23 varianten van de sudoku op te lossen, dus het kan het beste worden gebruikt met een computerondersteunde oplosser. Er zijn echter geen fancy algoritmen voor nodig om het te volgen. (ik gebruik mijn eigen zelfgekweekte niet-geoptimaliseerde python-programma, dus er is geen echte computer macht betrokken).

De notatie volgt de spreadsheetconventies (column = letter, row = number) (of schaken als je wilt).

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 

Ik heb schermafbeeldingen van de stappen en een korte uitleg van de methode op s Werelds moeilijkste Sudoku geplaatst. Omdat ik alleen geïnteresseerd ben in het oplossen van moeilijke puzzels door “onderbouwd raden”, ontdekte ik dat deze sudoku eigenlijk niet zo moeilijk is als geadverteerd (1 niveau van hypothese + 1 vooruitblik = 2 niveaus van hypothesen). In feite heb ik nog geen sudoku gevonden die meer dan 2 hypotheseniveaus + één lookahead vereist (= 3 hypotheseniveaus).

Opmerkingen

• Hoe goed doet uw oplosser eerlijk tegen sudoku ‘ s met 17 inzendingen? Bijv. theconversation.com/…
• @SimonStreicher De 17-clue Sudoku, u citeert is moeilijk, maar niet een van de moeilijkste sudokus in de context van mijn algoritme. Over het algemeen is er geen verband tussen het aantal aanwijzingen en de hardheid van een sudoku. Ik heb wat statistieken geplaatst over de sudokus die ik heb geanalyseerd.
• @SimonStreicher Ik heb analyseerde de lijst met top 95 sudokus (namelijk de 95 moeilijke puzzels ). Er zijn 5 sudukos met niveau moeilijk (2 niveaus van hypothesen zijn nodig), dat nog steeds 2 niveaus onder de 101 moeilijkste sudokus I ligt hebben gevonden.
• Bedankt voor de informatie, ik ‘ ben nog steeds bezig om dit allemaal te begrijpen, gelukkig is je website behoorlijk grondig.
• @SimonStreicher De kern ervan gaat over het verkleinen van de zoekruimte van het activeren van enkele waarden naar gemakkelijk herkenbare patronen (paren) die worden gebruikt om binaire beslissingen te genereren met verhoogde eliminatie van mogelijkheden. Bijv.cel1 staat 2 mogelijke waarden toe v1 en v2, cel2 laat dezelfde mogelijke waarden toe, maar daarnaast een of meer andere mogelijkheden v3, v4, v5. Daarom zijn cel1 en cel2 een paar (beide bevatten v1 en v2) of kan cel 2 alleen een van v3, v4, v5 zijn. Deze hypothese wordt vervolgens gecontroleerd.

Hoewel deze puzzel maar één oplossing heeft, er werken geen bekende patronen aan, behalve een iets intelligentere gok-en-check. Het aantal stappen dat je vooruit moet kijken om aanwijzingen weg te nemen, is hier de metriek, en deze puzzel heeft negen opeenvolgende gissingen nodig om een oplosbare toestand te bereiken.

De oplosser op SudokuWiki kan het “niet krijgen omdat het simpelweg te lang zou duren om het in Javascript te doen, en het is niet geprogrammeerd om getallen te raden.

De oplossing vereist dat iemand de waarden van kwadraten aanneemt en vervolgens de puzzel verkleint om te zien of je meer aannames nodig hebt – als je dat doet, maak dan een andere en ga verder. Het is in wezen een diepgaande zoektocht naar de mogelijke oplossingen. De oplosser op sudoku-oplossingen komt met de oplossing voor deze puzzel, maar wanneer hem wordt gevraagd om de stappen te geven, verklaart hij:

Deze oplosser kon de puzzel niet volledig logisch oplossen, dit betekent niet dat er geen logische oplossing is.

en slaagt er dan niet in om enige stappen te vermelden die het heeft gebruikt om het op te lossen. Dit gebeurt alleen wanneer de oplosser brute-force branching-raden moet gebruiken om de oplossing te vinden.

Als resultaat kan ik zelf op geen enkele manier redelijkerwijs een hoe deze puzzel oplossen-antwoord geven, aangezien dat zou betekenen dat je deze specifieke ketens moet vinden en moet uitleggen waarom de andere enorme hoeveelheid ketens niet “werkt.

Maar zo doe je het: neem aan dat een vierkant een getal is, dan een ander, dan nog een, en blijf kijken totdat je een reeks hebt gevonden die nog steeds klopt en je in staat stelt de puzzel op te lossen, of je bent op een tegenspraak gekomen en moet een back-up maken en het opnieuw proberen. Ik ben bang dat ik denk dat dit het beste antwoord is dat je op deze vraag kunt krijgen.

Aangezien je wel om een oplossing voor de puzzel hebt gevraagd, kan ik die geven (muis over het spoilerblok):

Reacties

• Goede oude recursie.
• Ik heb het opgelost met een recursiediepte van maximaal 2 keer raden. De ” Naked Singles ” strategie werd in totaal 61812 keer uitgevoerd (na wat caching op een hoger niveau, zonder dat het aantal runs in de miljoenen is), de ” Hidden Singles ” strategie 32892 keer (plus nog eens 28920 die werden bediend vanuit een cache) en een zoekopdracht met diepte slechts 1 werd uitgevoerd 256 keer en nog eens 15 keer uit de cache geserveerd (op elk punt werd slechts één keer raden gedaan, hoewel ik geloof dat de meeste van deze runs daadwerkelijk binnen de volgende zijn gebeurd), en de zoekopdracht op twee niveaus (waarbij je ‘ twee keer raden) maar één keer werd uitgevoerd en kreeg het.
• (dit is ook de enige puzzel die ‘ t crack met mijn programma met slechts EEN niveau van raden)

Download de premier van Singapore “s Sudoku-oplosser en voer deze puzzel in (ALLEEN als je ECHT vastzit). Geloof het of niet, die premier heeft een behoorlijk robuust programma gemaakt, en hoewel het lijkt alsof het daar een tijdje vastloopt, komt het uiteindelijk uit met de volgende oplossing:

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

Blijkbaar is het echter mogelijk om met logica op te lossen, volgens de man die deze puzzel heeft uitgevonden. Het kostte de oplossers gewoon 24 uur om het te doen.

Opmerking: bij deze puzzel staat de 1 op de 7e regel in een andere positie dan bij de vraag. Deze puzzel heeft meerdere oplossingen.

Reacties

• Ik betwijfel of deze originele puzzel meerdere oplossingen heeft (als dat is wat geïmpliceerd is). Jouw input voor de PM ‘ s oplosser is waarschijnlijk fout: rij 3, kolom 7 wordt als invoer opgegeven als ” 1 “, niet ” 7 ” (een van de waarnemingen). Gegeven de juiste invoer voor de exe, geeft het de bekende oplossing weer.
• @SimonStreicher de verkeerde invoer is in rij 7 kolom 3 waar de 7 een 1 zou moeten zijn
• Blijft het langer dan 5 seconden hangen? Mijn zeer eenvoudige oplosser slaagt erin om het daarover te krijgen tijdshoeveelheid.

Om een andere computergebaseerde oplossing toe te voegen, gebruik dan de MiniZinc-modelleertaal kunt u het volgende programma schrijven:

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

Samen met de juiste gegevens bestand:

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

En met behulp van de standaard oplosser op een redelijk standaard laptop komt de oplossing uit in 100 ms, wat de C ++ implementatie van PM Lee met een aanzienlijke marge.

Reacties

• Is dit algoritme gebaseerd op lineaire programmering?
• Het ‘ s in hetzelfde rijk – de oplosser is een oplosser voor het programmeren van beperkingen, die goed werkt omdat het probleem niet ‘ t echt lineair is, maar het is een aantal beperkingen. Het gebruikt een combinatie van heuristieken om de ruimte van mogelijke oplossingen te verkleinen met enkele vrij eenvoudige zoekmethoden.
• Ik ‘ ben onder de indruk. Mijn handleiding, heel eenvoudig dus lver in Kotlin verslaat het in ongeveer 5 seconden op mijn laptop, met een zoekdiepte van maximaal 2.