Kuinka voin ratkaista maailman ' vaikeimman sudokun?

Yksittäisten arvojen arvailu ensin syvyyshaulla on alle optimaalisen.

Tässä on siis päättelyketju, joka perustuu laajimpaan hypoteesiin / epävarmuuteen (jota poikapoikani kutsuu vastahakoisesti ”koulutetuksi arvaukseksi”).

Pelkästään ketjun seuraaminen, mukaan lukien ristiriidat, edellyttää ratkaista sudokun 23 muunnosta, joten sitä on parasta käyttää tietokoneavusteisen ratkaisijan kanssa. Se ei kuitenkaan vaadi hienoja algoritmeja sen seuraamiseksi. (Käytän omassa kodissani kasvatettua optimoimatonta python-ohjelmaa, joten todellista tietojenkäsittelyä ei ole joko voimaa).

Merkintätapa noudattaa laskentataulukon käytäntöjä (sarake = kirjain, rivi = numero) (tai shakkia, jos haluat).

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 

Olen asettanut näyttökuvia vaiheista ja nopean selityksen menetelmästä Worlds Hardest Sudokussa . Koska olen kiinnostunut vain vaikeiden pulmien ratkaisemisesta ”koulutetulla arvauksella”, huomasin, että tämä sudoku ei todellakaan ole niin kovaa kuin mainostetaan (yksi hypoteesitaso + 1 ulkonäkö = 2 hypoteesitasoa). Itse asiassa en ole vielä löytänyt sudokua, joka vaatii enemmän kuin 2 hypoteesitasoa + yhden näkökentän (= 3 hypoteesitasoa).

Kommentit

• Kuinka hyvin ratkaisijasi pärjää sudoku ’ s: ssä 17 merkinnällä? Esimerkiksi. theconversation.com/…
• @SimonStreicher 17-vihjeinen sudoku, johon viittaat on kova, mutta ei kovimpien sudokusten joukossa algoritmini yhteydessä. Yleensä vihjeiden lukumäärän ja sudokun kovuuden välillä ei ole korrelaatiota. Olen laatinut joitain tilastoja analysoimistani sudokuksista.
• @SimonStreicher Minulla on analysoi 95 suosituimman sudokun luettelon (nimittäin 95 kovat palapelit ). Sudukoja, joissa on hard -taso (5 hypoteesitasoa tarvitaan), on 5, mikä on edelleen 2 tasoa alle 101 kovimman sudokuksen I löysin.
• Kiitos tiedoista, yritän edelleen ymmärtää kaiken tämän, onneksi verkkosivustosi on melko perusteellinen.
• @SimonStreicher Sen ydin on hakutilan pienentäminen yksittäisten arvojen aktivoinnista helposti tunnistettaviksi kuvioiksi (pareiksi), joita käytetään binaaristen päätösten luomiseen lisäämällä mahdollisuuksia. Esimerkiksi.solu1 sallii 2 mahdollista arvoa v1 ja v2, solu2 sallii samat mahdolliset arvot, mutta lisäksi yhden tai useamman muun mahdollisuuden v3, v4, v5. Siksi solu1 ja solu2 ovat joko pari (molemmat sisältävät v1 ja v2) tai solu 2 voi olla vain yksi ryhmistä v3, v4, v5. Tämä hypoteesi tarkistetaan sitten.

Tälle palapelille, vaikka sillä on yksi ja ainoa ratkaisu, mikään tunnettu kuvio ei toimi siinä, paitsi hieman älykkäämpi arvaus ja tarkistus. Etenemisvaiheiden lukumäärä eteenpäin vihjeiden vähentämiseksi on tässä mittari, ja tämä palapeli tarvitsee yhdeksän peräkkäistä arvausta ratkaistavan tilan saavuttamiseksi.

SudokuWikin ratkaisija ei voi saada sitä, koska Javascriptin tekeminen kestää yksinkertaisesti liian kauan, eikä sitä ole ohjelmoitu arvaamaan numeroita.

Ratkaisu vaatii yhden ottamaan neliöiden arvot ja vähentämään sitten pulmapeliä nähdäksesi, tarvitsetko lisää oletuksia – jos tarvitset, tee toinen ja jatka. Se on perusteellisuushaku mahdollisista ratkaisuista. sudoku-solutions -sovelluksen ratkaisija on keksinyt ratkaisun tähän palapeliin, mutta kun häntä pyydetään antamaan vaiheet, hän ilmoittaa:

Tämä ratkaisija ei pystynyt ratkaisemaan palapeliä täysin logiikan avulla, tämä ei tarkoita sitä, ettei loogista ratkaisua ole.

ja ei heti ilmoita mitään sen ratkaisemiseen käytetyistä vaiheista. Tämä tapahtuu vain silloin, kun ratkaisijan on käytettävä raakaa voimaa haarautuvaa arvausta ratkaisun löytämiseksi.

Tämän seurauksena en voi mitenkään tarjota kohtuullisesti vastausta ”miten ratkaista tämä palapeli”, koska niin se merkitsisi näiden erityisten ketjujen löytämistä ja selittämistä, miksi muut valtavat ketjut eivät toimi.

Mutta niin teetkin: oletetaan, että neliö on luku, sitten toinen, sitten toinen, ja jatka tarkistamista, kunnes olet tullut sekvenssiin, jolla on vielä järkevää ja jonka avulla voit ratkaista pulman, tai olet tullut ristiriitaan ja sinun on varmuuskopioitava ja yritettävä uudelleen. Pelkään mielestäni, että tämä on paras vastaus, jonka voit saada tähän kysymykseen.

Koska pyysit pulmalle ratkaisua, voin kuitenkin tarjota sen (hiiren osoittimen spoileri):

Kommentit

• Vanha hyvä rekursio.
• Onnistuin ratkaisemaan sen enintään 2 arvauksen rekursiosyvyydellä. ” Naked Singles ” -strategia suoritettiin yhteensä 61812 kertaa (jonkin verran välimuistin tallentamisen jälkeen korkeammalla tasolla, ilman että juoksumäärä on miljoonina), ” Piilotetut kaksinpelit ” -strategia 32892 kertaa (plus toinen 28920, jotka annettiin välimuistista) ja haku, jonka syvyys oli vain 1, suoritettiin 256 kertaa ja palveli välimuistista vielä 15 kertaa (kussakin vaiheessa tehtiin vain yksi arvaus, vaikka uskon, että suurin osa näistä ajoista tapahtui todella seuraavassa), ja kaksitasoinen haku (jossa ’ teit 2 arvausta) juoksi vain kerran ja sai sen.
• (myös tämä on ainoa palapeli, joka ei onnistunut ’ ei murtaudu ohjelmani kanssa vain yhdellä arvaustasolla)

Lataa Singaporen pääministerin Sudoku-ratkaisija ja anna sille tämä palapeli (VAIN jos olet todella jumissa). Uskokaa tai älkää, tuo pääministeri teki melko vankan ohjelman, ja vaikka näyttää siltä, että se jumittuu hetkeksi siellä, se tulee lopulta esiin seuraavalla ratkaisulla:

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

Ilmeisesti on mahdollista ratkaista logiikalla, tämän palapelin keksinän miehen mukaan. Ratkaisijoille kesti vain 24 tuntia sen tekemiseen.

Huomaa: Tässä palapelissä on yksi 7. rivillä eri paikassa kysymyksenä. Tässä palapelissä on useita ratkaisuja.

Kommentit

• Epäilen, että tällä alkuperäisellä palapelillä on useita ratkaisuja (jos näin on). Palautteesi PM ’ ratkaisija on todennäköisesti väärä: rivi 3, sarake 7 annetaan syötteenä nimellä ” 1 ”, ei ” 7 ” (yksi havainnoista). Ottaen huomioon oikean syötteen exelle, se tuottaa tunnetun ratkaisun.
• @SimonStreicher väärä syöte on rivin 7 sarakkeessa 3, jossa 7: n tulisi olla 1
• Juuttuuko se yli 5 sekunniksi? Hyvin yksinkertainen ratkaisijani onnistuu saamaan sen siitä ajan määrä.

Lisää vain toinen tietokonepohjainen ratkaisu ja käytä sitten MiniZinc-mallinnuskieli voit kirjoittaa seuraavan ohjelman:

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

Oikeiden tietojen ohella tiedosto:

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

Ja oletusratkaisijan käyttäminen melko tavallisella kannettavalla tietokoneella, ratkaisu tulee ulos 100 ms: ssä, mikä voittaa PM Leen C ++ -toteutuksen huomattavasti marginaali.

Kommentit

• Perustuuko tämä algoritmi lineaariseen ohjelmointiin?
• Se ’ s samassa kentässä – ratkaisija on rajoitteen ohjelmointiratkaisija, joka toimii hyvin, koska ongelma ei ole ’ t todella lineaarinen, mutta se on joukko rajoituksia. Se käyttää Heuristiikan yhdistelmä mahdollisten ratkaisujen tilan pienentämiseksi joillakin melko perustavanlaatuisilla hakumenetelmillä.
• I ’ m vaikuttunut. Oman käsikirjani, hyvin yksinkertainen, joten Kotlinin lver voittaa sen noin viidessä sekunnissa kannettavalla tietokoneellani käyttäen korkeinta 2 hakusyvyyttä.