Algoritmi za reševanje igre Sudoku

Algoritmi za reševanje igre Sudoku

Avtor: Maja Dolinar

Opis igre sudoku

Sudoku je igra, kjer imamo kvadrat, ki je razdeljen na devet večjih kvadratov in vsak od teh devetih kvadratov je razdeljen še na devet manjših. Torej oblike:

(http://www2.nauk.si/files/455/prazen sudoku.png)
prazen sudoku
(http://www2.nauk.si/files/455/primer_sudoku.png)
primer sudoku-ja

V tej mreži je razporejenih že nekaj števk, naša naloga pa je, da celotno mrežo zapolnimo s števkami. In sicer pod pogoji:

  • v vsaki vrstici so vse števke od 1 do 9 (vsaka natanko enkrat),
  • v vsakem stolpcu so vse števke od 1 do 9 (vsaka natanko enkrat),
  • v vsakem od devetih večjih kvadratov so vse števke od 1 do 9 (vsaka natanko enkrat). To je osnovna verzija te igre, sedaj obstaja sicer že več različic, a jaz sem se omejila le na osnovno verzijo.

Reševanje 'na roke'

Ponavadi najprej rešimo kvadratke, kjer je možna le ena ena števka. Torej, da imamo le eno možnost. Npr.

(http://www2.nauk.si/files/455/resevanje_na_roke1.png)
Primer, ko števko lahko napišemo takoj
Na mestu, ki je obarvano ne more biti nobena druga števka kot 3. Najprej pregledamo cel sudoku in poiščemo čimveč takšnih primerov.
(http://www2.nauk.si/files/455/resevanje_na_roke2.png)
Primer, ko smo našli 'dvojčka' v vrstici.
Nato pogledamo, če obstajajo kje tako imenovani N-terčki.
Npr. dvojčki: Kadar najdemo dva kvadratka v isti vrstici ali stolpcu ali kvadratu, kjer lahko v prvi kvadratek vstavimo samo a ali b in v drugega lahko prav tako vstavimo le a in b, smo našli dvojčka. To pomeni, da lahko v tej vrstici ali stolpcu ali kvadratu v preostalih kvadratkih možnosti a in b preprosto brišemo. A in b bosta zasedla natanko ta dva kvadratka in iz tega sledi, da jih na drugih mestih ni.

Reševanje 'na roke' - pomoč z dvojčki

(http://www2.nauk.si/files/455/resevanje_na_roke3.png)
Primer, ko smo našli 'dvojčka' v vrstici.

V takem primeru se zna poenostaviti veliko možnosti in včasih se kakšni kvadratki razrešijo tako rekoč sami.

To pa ne velja le za dva kvadratka, vendar za katerokoli število od 2 do 9. Torej, če najdemo 3 kvadratke, kjer ima vsak od njih natanko 3 enake možnosti, lahko te 3 možnosti iz ostalih kvadratkov (v stolpcu ali vrstici ali kvadratu) mirno pobrišemo.

(http://www2.nauk.si/files/455/resevanje_na_roke4.png)
V zelenih poljih lahko zaradi rumenega dvojčka brišemo 8 in 9.
(http://www2.nauk.si/files/455/resevanje_na_roke5_0.png)
Iz vrstice smo izbrisali 8 in 9.Vidimo, da se v 7.stolpcu in obravnavani vrstici kvadratek razreši sam. Edina možnost je števka 2.

Algoritem lokalne optimizacije z ohlajanjem

Obstaja tudi algoritem Simulirano ohlajanje. Pri tem algoritmu izberemo eno od vej s katero se najbolj bližamo končnemu rezultatu. (Pri sudokuju bi lahko bile veje kar možnosti, ki jih lahko vstavimo v prvi prazen kvadratek). To naredimo na vsakem koraku. Predstavljamo si, da je začetno stanje neka temperatura T. To temperaturo želimo spraviti na nič, oziroma želimo priti do optimalnega minimuma:

(http://www2.nauk.si/files/455/ohlajanje1.png)
T moramo spraviti v globalni minimum.

Od tukaj tudi ime ohlajanje. S tem postopkom ni nujno da pridemo do globalnega minimuma. Lahko, da smo se 'ustavili' v lokalnem in ne globalnem minimumu. V tem primeru moramo temperaturo malo 'povečati', torej moramo 'problem segreti'. Vendar pa le do te točke, da se potem zopet spustimo po krivulji navzdol in tako temperaturo zopet nižamo. V tem primeru imamo neko kriterijsko funkcijo, ki nam pove v katerem primeru se splača segrevati in morda nekje obstaja še manjša vrednost, torej trenutno še nismo v globalnem minimumu ampak smo se le ustavili v lokalnem minimumu. Iščemo torej globalni minimum in vrednost temperature T želimo spraviti na nič. S pomočjo kriterijske funkcije se odločimo ali smo že prišli do rešitve, ali se nam splača še malo 'segreti' naš T in ga potem spet ohladiti na iskano vrednost.

Ker je pri sudoku-ju malo težje določiti kakšna je kriterijska funkcija, tega algoritma nisem napisala, sem pa le na kratko opisala za kaj pri tem algoritmu gre.

Algoritem razveji in omeji

Algoritem razveji in omeji je bolj znan za reševanje 0/1 nahrbtnika, primeren pa je tudi za druge probleme. Gre se za to, da problem najprej 'razvejimo' in nato veje omejimo s pomočjo kriterijske funkcije. Usmerimo se v smeri veje, kjer izgleda, da bomo prišli do najboljše rešitve.

Pri sudokuju bi npr. lahko za vsak prazen kvadratek napisali seznam možnosti, ki jih lahko vstavimo v ta kvadratek.

  • S pomočjo omejevalne (kriterijske) funkcije bi se usmerili v tisto možnost, ki bi bila najbolj obetavna. Lahko bi npr. sešteli dolžine seznamov možnosti vseh praznih kvadratkov v sudokuju.
  • Potem pa bi vstavili prvo možnost v prvi prazen kvadratek in bi zopet sešteli dolžine seznamov možnosti. * Potem bi vstavili drugo možnost prvega praznega kvadratka v ta kvadratek in zopet sešteli dolžine vseh seznamov možnosti.
  • In tako bi naredili za vse možnosti iz seznama možnosti prvega praznega kvadratka.
  • Iz seznama bi izbrali tisto možnost, ki je izračunala najmanjšo vsoto in jo vstavili v sudoku.
  • Potem bi pogledali naslednji prazen kvadratek in njegov seznam možnosti.
  • Izbrali bi spet prvo od možnosti in jo vstavili v sudoku.
  • Sešteli bi dolžine možnosti seznamov in tako naredili za vsako možnost v tem seznamu možnosti. Zopet bi izbrali tisto možnost, ki nam da najmanjšo vsoto (to pomeni, če vstavimo možnost, ki da najmanjšo vsoto, je z vstavitvijo te možnosti veliko izbir odpadlo, kar naj bi nas kmalu pripeljalo do prave rešitve).
  • Ni pa nujno, da nas izbira te veje res pripelje do pravega rezultata oz. do rešenega sudokuja. V tem primeru, bi se morali vračati do ene veje prej in izbrati drugo možnost. Vračali bi se tako dolgo, dokler ne bi enkrat res prišli do končne rešitve.

Zopet je pri sudoku-ju malo težje izbrati omejevalno funkcijo, zato tudi tega algoritma nisem sprogramirala ampak le na kratko opisala.

Kot sem omenila, nas omejevanje s tako funkcijo ne pripelje nujno do rešitve in bi se morali vračati na eno ali več vej nazaj. To je praktično enako kot, če ne bi imeli omejevalne funkcije. Enak algoritem kot je razveji in omeji, le brez omejevalne funkcije je algoritem s sestopanjem.

Algoritem s sestopanjem1

Iz prejšnje prosojnice je razvidno, da je to praktično enak algoritem kot razveji in omeji, le da je brez omejevalne oz. kriterijske funkcije.

Oglejmo si kodo v Pythonu, s pomočjo katere lahko rešite sudoku-je.

(http://www2.nauk.si/files/455/sestopanje1.png)
Vračanje številk kvadratov, vrstice in stolpcev iz pozicije.
Prva funkcija vrne številko kvadrata v katerem se nahaja izbrana pozicija.
(http://www2.nauk.si/files/455/kvadrati1.png)
Oštevilčenje kvadratov.
(http://www2.nauk.si/files/455/vrstice1.png)
Oštevilčenje vrstic.
(http://www2.nauk.si/files/455/stolpci1.png)
Oštevilčenje stolpcev.

Algoritem s sestopanjem2

(http://www2.nauk.si/files/455/sestopanje2.png)
Vračanje sosedov.
Vračanje vseh sosednjih indeksov v kvadratu, kjer je izbrani indeks ali v vrstici ali v stolpcu.

Algoritem s sestopanjem3

(http://www2.nauk.si/files/455/sestopanje3.png)
Preverjanje vstavljene števke.

Preverjamo, ali je vstavljena števka vstavljena pravilno.

Najprej poiščemo v katerem kvadratu, v kateri vrstici in v katerem stolpcu se nahaja vstavljena števka.

Potem pa preverimo, ali je že kje v tej vrstici ali stolpcu ali kvadratu ta števka. V tem primeru funkcija vrne False, drugače pa True.

Algoritem s sestopanjem4

(http://www2.nauk.si/files/455/sestopanje4.png)
Vrne seznam vseh števil, ki so možne na tem mestu.
Ko je kvadratek prazen, poženemo to funkcijo in dobimo števila, ki so možna na tem mestu (tista števila, ki jih še ni v kvadratu ali vrstici ali stolpcu).

Sedaj smo definirali vse pomožne funkcije in se lahko lotimo reševanja sudokuja s pomočjo algoritma sestopanja.

  • Najprej preverimo, če je vnešena dolžina seznama res 81.
  • Potem pa se lotimo vseh kvadratkov, kjer je v seznamu ničla. Torej tisti, kateri so še prazni.
  • Izračunamo možnosti in vzamemo prvo iz seznama možnosti. Vstavimo jo v seznam na mesto, kjer je bil prej prazen kvadratek. S pomočjo rekurzije preverimo naprej naslednja mesta. Ko pridemo do mesta 81 (oz. 80 v seznamu) pomeni, da smo prišli do konca in, če so vsa števila vnešena pravilno, vrnemo seznam. To je končna rešitev.
  • V primeru, ko je v seznamu napisana fiksna številka, spremenljivki mesto dodamo 1 in preverjamo naprej naslednja mesta.
  • Ves čas imamo poleg kopijo prvotnega seznama za preverjanje, ko gremo eno vejo nazaj. Tako lahko v vsakem trenutku pogledamo katera mesta v sudoku-ju so bila že prvotno izpolnjena in katera prazna.

Koda funkcije je na naslednji strani.

Algoritem s sestopanjem5

(http://www2.nauk.si/files/455/sestopanje5.png)
Rešuje sudoku s pomočjo sestopanja.

Algoritem s sestopanjem6

(http://www2.nauk.si/files/455/sestopanje6.png)
Lep izpis.
Uporabniku bolj prijazna je funkcija vrni_resitev, ki kot vhodni argument dobi le seznam dolžine 81. Znotraj funkcije se ustvari kopija seznama in spremenljivki konec ter mesto se nastavita na 0. To pomeni, da začnemo preverjati in reševati sudoku na mestu 0 ter, da še nismo končali pregleda(konec=0 pomeni delovanje programa, konec=1 gre ven iz prve zanke in konec=2 nam da končno funkcijo). Požene se torej prejšnja funkcija resi_sudoku.

Če želite imeti opisan program, ga dobite tukaj:Algoritem sestopanja

Algoritem s sestopanjem-primer

(http://www2.nauk.si/files/455/primerAlgoritma.PNG)
Primer delovanja algoritma.

OPOMBA:

Sam algoritem sicer dela precej počasi, vendar pride do rešitve. Hitreje bi bilo seveda, če bi uporabili še omejevalno funkcijo seveda, če bi vedeli kakšno. Težje sudokuje program računa precej dolgo, a vseeno ni čisto neuporaben :).

Filmček delovanja programa

Kviz1

S katerimi algoritmi lahko rešimo sudoku?

Preveri

Pravilno!

Naprej

Žal, poskusi znova! Ponovi

Žal, poskusi znova!

Ponovi

Kviz2

V kateri od spodnjih slik se skriva dvojček pri sudokujih?

(http://www2.nauk.si/files/455/kviz2.PNG)
B
C
A

Pravilno!

Naprej

Žal, poskusi znova!

Ponovi

Kviz3

Poveži pravilno reševanje sudokuja!

v kvadratu 3x3 so napisane cifre 1,3,5
v vrstici so že napisane cifre 1,5,6
v stolpcu so že napisane cifre 3,4,6
dodamo lahko še 6
dodamo lahko še 3
dodamo lahko še 1

Naprej

Pravilno!

Naprej

Žal, poskusi znova!

Ponovi

Literatura

0%
0%