Tekoälypohjainen ratkaisu Sudokuun

Tekoälypohjainen ratkaisu Sudokuun

Aikaleima: 29. tammikuuta 2024 9
Lähdesolmu: 3091242

29. tammikuuta on kansallinen palapelipäivä, ja sen kunniaksi olemme luoneet hauskan blogin, jossa kerrotaan kuinka ratkaista Sudoku tekoälyn (AI) avulla.

esittely

Ennen Wordlen, The Sudoku palapeli oli raivoa ja se on edelleen erittäin suosittu. Viime vuosina käyttö optimointi menetelmiä pulman ratkaisemiseksi on ollut hallitseva teema. Katso "Sudoku-palapelin ratkaiseminen optimoinnin avulla Arkievassa".

Nykyisin tekoälyn käyttö keskittyy koneoppimiseen, joka kattaa laajan valikoiman menetelmiä lasso-regressiosta vahvistusoppimiseen. Tekoälyn käytössä on uudelleen käsitellä monimutkaisia aikataulutus haasteita. Yksi tapa, haku backtracking, on yleisesti käytetty ja sopii täydellisesti Sudokuun.

Tämä blogi sisältää yksityiskohtaisen kuvauksen siitä, kuinka tätä menetelmää käytetään Sudokun ratkaisemiseen. Kuten käy ilmi, "backtracking" löytyy optimointi- ja koneoppimismoottoreista, ja se on Arkievan aikataulutuksessa käyttämän edistyneen heuristiikan kulmakivi. Algoritmi on toteutettu "Array Programming Language" -kielellä, funktioorientoituneella ohjelmointikielellä, joka käsittelee rikas joukko taulukkorakenteita.

Sudokun perusteet

Wikipedia-sivulta: Sudoku on logiikkaan perustuva, kombinatorinen numerosijoittelupulma. Tavoitteena on täyttää 9×9 ruudukko numeroilla siten, että jokainen sarake, jokainen rivi ja jokainen yhdeksästä 3×3 aliruudukosta, jotka muodostavat ruudukon (kutsutaan myös "laatikoiksi", "lohkoiksi", "alueiksi", tai "alineliöt" sisältää kaikki numerot 1 - 9. Palapelin asettaja tarjoaa osittain valmiin ruudukon, jolla on tyypillisesti ainutlaatuinen ratkaisu. Valmiit palapelit ovat aina eräänlainen latinalainen neliö, joka rajoittaa yksittäisten alueiden sisältöä. Esimerkiksi sama yksittäinen kokonaisluku ei välttämättä näy kahdesti samalla 9 × 9 -pelilaudan rivillä tai sarakkeella tai missään 3 × 3 -pelilaudan yhdeksästä 9 × 9 -alialueesta.

Taulukossa 1 on esimerkkiongelma. Siinä on 9 riviä ja 9 saraketta, yhteensä 81 solua. Jokaisella saa olla yksi ja vain yksi yhdeksästä kokonaisluvusta väliltä 1 - 9. Aloitusratkaisussa solulla on joko yksi arvo – joka kiinnittää tämän solun arvon kyseiseen arvoon, tai solu on tyhjä, mikä osoittaa, että tarvitsemme löytääksesi arvon tälle solulle. Solun (1,1) arvo on 2 ja solun (6,5) arvo 6. Solu (1,2) ja solu (2,3) ovat tyhjiä, ja algoritmi löytää arvon näille soluille.

Komplikaatio

Sen lisäksi, että solu kuuluu yhteen ja vain yhteen riviin ja sarakkeeseen, se kuuluu yhteen ja vain yhteen laatikkoon. Laatikoita on 1, ja ne on merkitty värillä taulukossa 9. Taulukossa 1 käytetään yksilöllistä kokonaislukua välillä 2-1 jokaisen laatikon tai ruudukon tunnistamiseen. Solut, joiden rivin arvo on (9, 1 tai 2) ja sarakkeen arvo on (3, 1 tai 2), kuuluvat ruutuun 3. Laatikko 1 on riviarvot (6, 4, 5) ja sarakearvot (6, 7) , 8). Laatikon tunnus määritetään kaavalla BOX_ID = {9x(lattia((ROW_ID-3) /1)} + katto (COL_ID/3). Solulle (3) 5,7 = 6x(floor(3-5) ))/1) + katto (3/8)= 3×3 + 1 = 3+3.

Palapelin sydän

Löytääksesi yhden kokonaislukuarvon väliltä 1–9 kullekin tuntemattomalle solulle siten, että kokonaislukuja 1–9 käytetään kerran ja vain kerran jokaisessa sarakkeessa, jokaisessa rivissä ja jokaisessa laatikossa.

Katsotaanpa solua (1,3), joka on tyhjä. Rivillä 1 on jo arvot 2 ja 7. Nämä eivät ole sallittuja tässä solussa. Sarakkeessa 3 on jo arvot 3, 5,6, 7,9. Nämä eivät ole sallittuja. Laatikon 1 (keltainen) arvot ovat 2, 3 ja 8. Nämä eivät ole sallittuja. Seuraavat arvot eivät ole sallittuja (2,7); (3, 5, 6, 7, 9); (2, 3, 8). Yksilölliset arvot eivät ole sallittuja (2, 3, 5, 6, 7, 8, 9). Ainoat ehdokasarvot ovat (1,4).

Ratkaisutapa olisi antaa tilapäisesti 1 solulle (1,3) ja yrittää sitten löytää ehdokasarvoja toiselle solulle.

Ratkaisu taaksepäin: aloituskomponentit

Taulukon rakenne

Lähtökohtana on päättää taulukkorakenne lähdeongelman tallentamiseksi ja haun tukemiseksi. Taulukossa 3 on tämä taulukkorakenne. Sarake 1 on yksilöllinen kokonaislukutunnus jokaiselle solulle. Arvot vaihtelevat välillä 1 - 81. Sarake 2 on solun rivitunnus. Sarake 3 on solun saraketunnus. Sarake 4 on laatikon tunnus. Sarake 5 on solun arvo. Tarkkaile solulle ilman arvoa annetaan arvo nolla tyhjän tai nollan sijaan. Tämä pitää tämän "vain kokonaislukumatriisina" - suorituskyvyltään paljon parempi.

APL:ssä tämä matriisi tallennettaisiin 2-ulotteiseen taulukkoon, jonka muoto on 81 x 5. Oletetaan, että taulukon 3 elementit on tallennettu muuttujaan MAT. Esimerkkitoiminnot ovat:

Komento MAT[1 2 3;] nappaa MAT:n 3 ensimmäistä riviä
1 1 1 1 2
2 1 2 1 0
3 1 3 1 0
MAT[1 2 3; 4 5] varmistaa rivit 1, 2, 3 ja vain sarakkeet 4 ja 5
1
1
1
(MAT[;5]=0)/MAT[;1] etsii kaikki solut, jotka tarvitsevat arvon.

LISÄÄ TAULUKKO 3

Sanity Check: kaksoiskappaleet

Ennen haun aloittamista on tärkeää tarkistaa mielenterveys! Tämä on lähtökohtaisesti toteutettavissa oleva ratkaisu. On mahdollista Sudokulle, onko nyt kaksoiskappaleita missä tahansa rivissä, sarakkeessa tai laatikossa. Nykyinen lähtöratkaisu, esimerkiksi 1, on toteutettavissa. Taulukossa 4 on esimerkki, jossa aloitusratkaisussa on kaksoiskappaleita. Rivillä 1 on kaksi arvoa 2. Alueella 1 on kaksi arvoa 2. Funktio "SANITY_DUPE" käsittelee tätä logiikkaa.

Sanity Check: Asetukset soluille ilman arvoja

Erittäin hyödyllinen tieto olisi kaikki mahdolliset arvot solulle ilman arvoa. Jos ehdokkaita ei ole, tämä arvoitus ei ole ratkaistavissa. Solu ei voi ottaa arvoa, jonka sen naapuri on jo vaatinut. Kun käytetään taulukkoa 1 solulle (1,3,'1' – tämä viimeinen 1 on laatikkotunnus), sen naapurit ovat rivi 1, sarake 3 ja laatikko 1. Rivillä 1 on arvot (2,7); sarakkeessa 3 on arvot (3,5,6,7,9); laatikossa 1 on arvot (2,3,8). Solu (1,3.1) ei voi ottaa seuraavia arvoja (2,3,5,6,7,8,9). Solun (1,3,1) ainoat vaihtoehdot ovat (1,4). Solun (4,1,2) arvot 1, 2, 3, 5, 6, 7, 9 ovat jo käytössä rivillä 4, sarakkeessa 1 ja/tai laatikossa 4. Ainoat ehdokasarvot ovat (4,8) . Unction "SANITY_CAND" käsittelee tätä logiikkaa.

Taulukko 5 näyttää ehdokkaat, esimerkiksi 1 hakuprosessin alussa. Jos solulle on jo määritetty arvo aloitusehdoissa (taulukko 1), tämä arvo toistetaan ja näytetään punaisena. Jos solussa, joka tarvitsee arvon, on vain yksi vaihtoehto, se näkyy valkoisella. Solun (8,7,9) yksittäinen arvo 7 on valkoinen. (2,5,8,4,3) vaaditaan naapurisarakkeella 7. (1, 2, 9) rivillä 8. (3,2,6) laatikolla 9. Vain arvoa 7 ei vaadita.

Sanity Check: Etsitkö ristiriitoja

Tieto, joka tunnistaa kaikki arvon tarvitsevien solujen vaihtoehdot (julkaistu taulukossa 4), mahdollistaa ristiriidan tunnistamisen ennen hakuprosessin aloittamista. Ristiriita syntyy, kun kahdella solulla, jotka tarvitsevat arvon, on vain yksi ehdokas, ehdokasarvo on sama ja kaksi solua ovat naapureita. Taulukosta 4 tiedämme, että ainoa solu, joka tarvitsee arvon ja jolla on vain yksi ehdokas, on solu (8,7,9). Esimerkiksi 1, ei ole ristiriitaa.

Mikä olisi konflikti? Jos solun (3,7,3) ainoa mahdollinen arvo oli 7 (1, 6, 7 sijaan), kyseessä on ristiriita. Solu (8,7) ja solu (3,7) ovat naapureita – sama sarake. Jos solun (4,9,2) ainoa mahdollinen arvo olisi 7 (1, 2, 7 sijaan), tämä ei olisi ristiriita. Nämä solut eivät ole naapureita.

Sanity Check Yhteenveto

  1. Jos on kaksoiskappaleita, aloitusratkaisu ei ole mahdollinen.
  2. Jos solulla, joka tarvitsee arvon, ei ole ehdokkaita, tähän pulmaan ei ole mahdollista ratkaisua. Jokaisen solun ehdokasarvojen luetteloa voidaan käyttää vähentämään hakutilaa – sekä taaksepäin että optimoinnissa.
  3. Kyky löytää ristiriitoja osoittaa, että arvoitus ei ole mahdollista – ei ole ratkaisua – ilman hakuprosessia. Lisäksi se tunnistaa "ongelmasolut".

Paluuratkaisu: Hakuprosessi

Kun ydintietorakenteet ja mielenterveyden tarkastus ovat kunnossa, kiinnitämme huomiomme hakuprosessiin. Toistuva teema on jälleen tietorakenteiden saaminen paikoilleen hakua tukemaan.

Haun seuranta

Joukko Tracker pitää kirjaa tehdyistä tehtävistä

  1. Col 1 on laskuri
  2. Sarake 2 on tähän soluun määritettävissä olevien vaihtoehtojen määrä
    • 1 tarkoittaa yhtä vaihtoehtoa, 1 tarkoittaa kahta vaihtoehtoa jne.
    • 0 tarkoittaa – vaihtoehtoa ei ole käytettävissä tai nollausta (ei määritettyä arvoa) ja paluuta
  3. Sarake 3 on solu, jolle on määritetty arvoindeksinumero (1 - 81)
  4. Sarake 4 on arvo, joka on määritetty solulle seurantahistoriassa
    • Arvo 9999 tarkoittaa, että tämä solu oli silloin, kun umpikuja löydettiin
    • Kokonaisluvun 1–9 arvo on tälle solulle annettu arvo tässä hakuprosessin vaiheessa.
    • Arvo 0 tarkoittaa, että tämä solu tarvitsee määrityksen

Tracker-taulukkoa käytetään tukemaan hakuprosessia. Joukko TRACKHIST sillä on sama rakenne kuin jäljittimellä, mutta se säilyttää koko hakuprosessin historian. Taulukossa 6 on osa TRACKHISTista esimerkiksi 1. Se selitetään tarkemmin myöhemmässä osassa.

Lisäksi joukko PAV (vektorin vektori), pitää kirjaa tähän soluun aiemmin annetuista arvoista. Tämä varmistaa, että emme palaa epäonnistuneeseen ratkaisuun – samalla tavalla kuin TABUssa.

On valinnainen lokiprosessi, jossa hakuprosessi kirjoittaa jokaisen vaiheen.

Haun aloittaminen

Kun kirjanpito ja mielenterveystarkastus on tehty, voimme nyt aloittaa hakuprosessin. Vaiheet ovat:

  1. Onko jäljellä soluja, jotka tarvitsevat arvon? – Jos ei, olemme valmiita.
  2. Etsi jokaiselle solulle, joka tarvitsee arvon, kaikki mahdolliset vaihtoehdot kullekin solulle. Taulukossa 4 on nämä arvot ratkaisuprosessin alussa. Jokaisessa iteraatiossa tämä päivitetään soluille määritettyjen arvojen mukaiseksi.
  3. Arvioi vaihtoehdot tässä järjestyksessä.
    • Jos solussa on NOLLA vaihtoehtoja, aloita paluu
    • Etsi kaikki solut yhdellä vaihtoehdolla, valitse yksi näistä soluista, tee tämä tehtävä,
      1. ja päivitä seurantataulukko, nykyinen ratkaisu ja PAV.
    • Jos kaikissa soluissa on useampi kuin yksi vaihtoehto, valitse yksi solu ja yksi arvo ja päivitä
      1. ja päivitä seurantataulukko, nykyinen ratkaisu ja PAV

Käytämme taulukkoa 6, joka on osa ratkaisuprosessin historiaa (jota kutsutaan TRACKHISTiksi) kunkin vaiheen havainnollistamiseen.

Ensimmäisessä iteraatiossa (CTR=1) solulle 70 (rivi 8, sarake 7, laatikko 9) valitaan arvo. On vain ehdokas (7), ja tämä arvo on määritetty solulle 70. Lisäksi arvo 7 lisätään solun 70 aiemmin määritettyjen arvojen vektoriin (PAV).

Toisessa iteraatiosolussa 30 on annettu arvo 1. Tällä solulla oli kaksi ehdokasarvoa. Pienin ehdokasarvo määritetään solulle (vain mielivaltainen sääntö, jotta logiikkaa on helppo seurata).

Prosessi arvon tarvitsevan solun tunnistamiseksi ja arvon määrittämiseksi toimii hyvin iteraatioon (CTR) 20 asti. Solu 9 tarvitsee arvon, mutta ehdokkaiden määrä on NOLLA. Vaihtoehtoja on kaksi:

  • Tähän pulmaan ei ole ratkaisua.
  • Kumoamme (perutamme) joitakin tehtäviä ja valitsemme toisen polun.

Etsimme tätä lähinnä olevaa solukohdetta, jossa oli useampi kuin yksi vaihtoehto. Tässä esimerkissä tämä tapahtui iteraatiossa 18, jossa solulle 5 on annettu arvo 3, mutta solulle 5 oli kaksi ehdokasarvoa – arvot 3 ja 8.

Solun 5 (CTR = 18) ja solun 9 (CTR = 20) välillä solulle 8 annetaan arvo 4 (CTR = 19). Laitoimme solut 8 ja 5 takaisin "tarvitaan arvo" -luetteloon. Tämä kirjataan toiseen ja kolmanteen CTR=20-merkintään, joissa arvoksi asetetaan 0. Arvo 3 säilytetään solun 5 PAV-vektorissa. Tämä tarkoittaa, että hakukone ei voi määrittää arvoa 3 solulle 5.

Hakukone käynnistyy uudelleen tunnistaakseen arvon solulle 5 (jossa 3 ei enää ole vaihtoehto) ja määrittää arvon 8 solulle 5 (CTR=21). Se jatkuu, kunnes kaikilla soluilla on arvo tai on solu, jolla ei ole vaihtoehtoa eikä paluupolkua ole. Ratkaisu on esitetty taulukossa 7.

Huomaa, että jos soluun on useampi kuin yksi ehdokas, tämä on mahdollisuus rinnakkaiseen käsittelyyn.

Vertailu MILP-optimointiratkaisuun

Pintatasolla Sudoku-palapelin esitystapa on dramaattisesti erilainen. AI-lähestymistapa käyttää kokonaislukuja, ja se on millä tahansa mitalla tiukempi ja intuitiivisempi esitys. Lisäksi mielenterveyden tarkistimet tarjoavat hyödyllistä tietoa vahvemman koostumuksen tekemiseksi. MILP-esitys on loputon binaries (0/1). Binaarit ovat kuitenkin tehokkaita esityksiä nykyaikaisten MILP-ratkaisijoiden vahvuuden vuoksi.

Sisäisesti MILP-ratkaisin ei kuitenkaan säilytä binääriä, vaan käyttää harvaa taulukkomenetelmää kaikkien nollien tallentamisen poistamiseksi. Lisäksi algoritmit binäärien ratkaisemiseksi syntyivät vasta 1980- ja 1990-luvuilla. Vuoden 1983 lehti Crowder, Johnson ja Padberg raportoi yhdestä ensimmäisistä käytännön ratkaisuista optimointi binäärien avulla. He huomauttavat älykkään esikäsittelyn sekä haara- ja sidomenetelmien tärkeyden onnistuneen ratkaisun kannalta kriittisinä.

Viimeaikainen räjähdysmäinen rajoitusohjelmoinnin ja ohjelmistojen käyttö, kuten paikallinen ratkaisija on tehnyt selväksi tekoälymenetelmien käytön tärkeyden alkuperäisten optimointimenetelmien, kuten lineaarisen ohjelmoinnin ja pienimmän neliösumman, kanssa.

Aikaleima:

Lisää aiheesta Arkieva