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 :))
