Tuesday, June 27, 2006

sudoku


Verovatno ste svi čuli za igru Sudoku.
Pravila su vrlo jednostavna:
Dobijete matricu dimenzija 9x9, koja je dodatno izdeljena na 9 manjih matrica (3x3), u neka polja su upisani brojevi od 1 do 9 i vi treba da popunite celu matricu tako da se u svakom redu i koloni, ali i u unutrašnjoj matrici od 3 x 3 polja, nađu brojevi od 1 do 9, pri čemu se oni ne smeju ponavljati.
Jedan nemački matematičar izračunao je da je ukupan broj kombinacija u ovoj igri 6.670.903.752.021.072.936.960, što, kako negde pročitah, odgovara broju mikrona do najbliže zvezde.
Više o igri naravno možete pročitati na: http://en.wikipedia.org/wiki/Sudoku

Imao sam priliku da se igram malo sa ovim, i ono što sam napravio možete videti ovde.
U pitanju je JAVA aplet koji rešava bilo koji sudoku zadatak (koji ima rešenje, naravno). Ukoliko ima više rešenja, prikazaće prvo na koje naiđe.
Što se algoritma tiče, program prvo pokušava da na "pametan" način dođe do rešenja, znači gleda da li je vrednost nekog polja očigledna, zatim za sva ostala polja računa kandidate za vrednosti, pa na osnovu pravila (da u 1 vrsti, koloni ili maloj matrici svi elementi moraju biti različiti) poljima koja imaju samo 1 kandidata fiksira vrednost. I to se tako vrti dok ne dođe do trenutka u kome sva ne rešena polja imaju više kandidata, tako da ne postoji način da se utvrdi koje vrednosti treba fiksirati.
U tom trenutku u priču se uključuje backtracking algoritam, koji rekurzivno pokušava da pronađe prave vrednosti.
On radi tako što uzme prvo ne rešeno polje i fiksira mu prvog kandidata, zatim za takvu matricu pokušava da nadje rešenje. Ukoliko u nekom trenutku, posle primene svih gore pomenutih pravila bilo koje ne rešeno polje ostane bez kandidata, to je signal da nešto ne valja, i rekurzivna funkcija se vraća nazad i uzima prvog sledećeg kandidata.
Ukoliko neko želi, okačiću source , pa da ga zajedno prodiskutujemo. (naravno, pošto nisam koristio nikakav obfuscator, oni sa malo više znanja mogu i sami da vide source :))

4 comments:

Chupa said...

Extra.... obožavam probleme koji nisu rešeni u knjigama :) ... (možeš da dodaš appendix u knjizi iz Operacionih istraživanja :)

Prvo što me zanima... je sta podrazumevaš pod očigledne vrednosti na početku algoritma... jel je to situacija kada fali samo jedna vrednost u nizu? ...

Nego... jel sudoku uvek 9x9 ? ... bilo bi vrlo zanimljivo ako može da raste dimenzija problema... pa da se dođe u situaciju kada ne može da se reši jednim exhaustive-depthFirst algoritmom kakav je backTracking...

To naravno, ako nemamo sta drugo da radimo :) ... po principu: ako nemas problem, napravi si :)

Damjan said...

@chupa:
Oduvek sam voleo da rešavam mozgalice i ovaj sudoku me je oduševio kad sam se prvi put sreo sa njim.

Očigledne vrednosti su, kao što si i sam napisao situacije u kojima jedno polje ima samo jednog kandidata za vrednost. To znači da se 8 cifara (naravno različitih) nalazi u koloni, vrsti ili maloj matrici u kojoj se nalazi i to polje, pa je deveta cifra jedina koja može da bude vrednost tom polju.
Inače, ceo algoritam se svodi na računanje skupa kandidata za svako polje i fiksiranje vrednosti poljima koja imaju samo 1 kandidata.
Kandidati za jedno polje su ,naravno ,one vrednosti koje zbog vrednosti ostalih polja u vrsti, koloni i maloj matrici mogu biti "fiksirane" na tom polju.
Što se tiče dimenzija problema, ja se nisam igrao sa većim matricama, mada bi, sa malo prilagodjavanja ovaj applet mogao da reši i veće matrice. Sad.. koliko veće.. :) to bih morao da probam.
Iz tvojih pitanja znam da te interesuje da li bi mogla neka heuristika da se upotrebi za probleme većih dimenzija.. Pa sigurno da bi, ali konkretan odgovor nemam. Bilo bi ok da organizujemo neko pivo kod mene, tebe, zija ili gde već .. pa da probamo da smislimo neki pametan algoritam. (To naravno po onom tvom principu sa kraja komentara :) )

Dragana said...

Svaka cast Damjane, to je to.
A sta bi preporucio nama obicnim smrtnicima koji radimo olovkom, dodjemo do tacke kada je 56 polja popunjeno i jos nam fali 25 a vrednosti u njima su sve u parovima tipa (1,8)(1,8)pa (3,7)(3,7) pa (1,4)(1,4)... i samo na par mesta ima po 3 cifre. Da li operaciona istrazivanja imaju neki metod programiranja koji bi izbacio resenje i bez kompjutera, ovako olovkom i papirom. Kao sistem jednacina pa elementarna bazna transformacija ili tako nesto.

Damjan said...

Zdravo Dragana,

Koliko sam ja upoznat, za tu situaciju ne postoji rešenje sem backtracking algoritama.. što znači jedina varijanta je uzeti grafitnu olovku, odabrati nasumično jedan broj od tih koji su ostali kao kandidati, upisati njega u polje i nastaviti sa rešavanjem. Ukoliko ste imali sreće sudoku će biti rešen do kraja; ukoliko niste, treba obrisati sve brojeve koji su uneti posle onog koji je nasumično odabran, pa umesto njega staviti sledeći i nastaviti sa rešavanjem...
Inače, baš davno je bilo kada sam se bavio ovim, i nisam više "u toku", tako da je moguće da postoji i neka "pametna" metoda iz operacionih istraživanja koja bi ovo rešila, a za koju ja ne znam.

Pozdrav,
Damjan.