Popularna logička igra brojevima je oduševila svet. Da bi rešili slagalicu, nije nam potrebno znanje matematike, već logika i iskustvo. Manje je poznato da je Sudoku mnogo više od obične slagalice: igrajući je milioni ljudi zadiru u jedan od najkompleksnijih problema u kompjuterskoj nauci, a da toga nisu svesni.
autorka: Jasna Petrović
Matematičar Ojler: Tvorac „Latinskog kvadrata“ Naziv „Sudoku“ dolazi iz Japana kao skraćenica duže fraze "Suuji wa dokushin ni kagiru" koja grubo prevedeno znači „brojevi moraju ostati jedinstveni“. Iako ime potiče iz Japana korene ove logičke zagonetke nalazimo u Evropi i Americi. Poreklo današnjeg Sudokua dolazi iz 18. veka. Čuveni i hiperproduktivni (866 publikacija) švajcarski matematičar Leonard Ojler (Leonhard Euler) sačinio je tzv. Latinski kvadrat (Carré latin), koji se sastojao od NxN polja obeleženih sa N različitih simbola tako da se svaki simbol u svakom redu i svakoj koloni samo jedanput ponavlja. Koristeći ovaj koncept, 1979. godine američki časopis Dell (Dell Math Puzzles & Logic Problems) je po prvi put objavio kvadratnu slagalicu dimenzija 9x9 koja se sastoji od 9 manjih kvadrata dimenzija 3x3, tj. ono što danas nazivamo Sudoku.
Ova igra međutim doživljava pravi prodor u Japanu sredinom osamdesetih godina prošlog veka kada je prvi put objavljena u poznatom japanskom časopisu Nikoli. Novozelanđanin Wayne Gould je na svom putovanju po Japanu naučio da igra Sudoku, oduševio se njom, i narednih nekoliko godina razvijao kompjuterski program za generisanje ovih slagalica. Krajem 2004. godine pošlo mu je za rukom da ubedi londonske novine The Times da koristeći njegov program štampa dnevne Sudoku slagalice. Ubrzo su i druge britanske novine počele da štampaju svoje Sudoku slagalice. Igra je postala jako popularna, ne samo u Engleskoj, vec i u drugim zemljama: Nemačkoj, Austriji, SAD-u,…
Osnove Sudokua
Sudoku: Moguća startna pozicija
Pravila igre su vrlo jednostavna, iako rešenje često nije. Slagalicu čini kvadrat. Broj polja je najčešće 81 (9x9), koji je podeljen na manje kvadrate (podkvadrate) dimenzija 3x3 polja. Kao početni „tragovi“, u nekoliko polja su unešene cifre, a cilj igre je da se ostala prazna polja popune tako da na kraju svaki red, kolona i podkvadrat sadrze cifre od 1 do 9 samo jedanput. Sudoku slagalice su u zavisnosti od težine uglavnom podeljene na „lake“, „srednje“ i „teške“. Treba naglasiti da težinu slagalice ne određuje samo broj unapred datih cifara, već i njihov razmeštaj u kvadratu. Strategija rešavanja može kombinovati nekoliko osnovnih metoda: skeniranje, obeležavanje, i analizu.
Sudoku slagalica po pravilu ima samo jedno moguće rešenje. U međuvremenu su se pojavile i slagalice sa 16x16 polja kao i druge još komplikovanije varijante, na primer kombinacija igara Sudoku i Kakuro nazvana Killer Sudoku. Postoji i Sudoku za decu, koji se sastoji od malog broja polja.
Sudoku i matematika
Rešen Sudoku: svaka cifra pojavljuje se samo jednom u svakom redu, koloni i podkvadratu
Činjenica da niko ne zna algoritam kojim se uvek dolazi do rešenja bez prethodnog isprobavanja ogromnog broja kombinacija stavlja Sudoku u klasu tzv. NP-potpunih problema (NP je skraćenica za „Non-deterministic Polynomial time”) kojoj takođe pripadaju mnogi praktični problemi kao što su sekvenciranje gena i rutiranje mreže. NP-potpuni problemi su najkompleksnija vrsta NP-problema i karakterišu se teškoćom pronalaženja rešenja, koje podrazumeva proveravanje najčešće nebrojeno mnogo kombinacija. Na primer, nedavno je izračunato da broj mogućih Sudoku-a dimenzije 9x9 iznosi neverovatnih 6,67090375202107293696 · 1021. Jedan od najpoznatijih NP-problema je problem trgovačkog putnika poznat sigurno svima koji su se ikada ozbiljnije bavili pisanjem kompjuterskih algoritama (http://www.tsp.gatech.edu/). Ovaj problem intrigira mnoge naučnike još od njegove postavke davne 1930. godine. Iako se može definisati u samo jednoj rečenici lakoj za razumevanje, jako je težak za rešavanje.
Sudoku pruža idealnu mogućnost istraživanja klase NP-potpunih problema. Naime, pronalazak efikasnog algoritma za rešavanje NP-potpunog problema bi automatski omogućio rešavanje bilo kog NP-problema. Jedan broj stručnjaka smatra da takvo rešenje ne postoji, ali kontinuiran napredak i nalaženje sve bržih rešenja u ovoj oblasti je evidentan.
Značajni pomaci u razvoju algoritama za rešavanje ovih problema nastali istraživanjem Sudoku-a i Ojlerovih Latinskih kvadrata dolaze od prof. Carla Gomesa sa Cornell Univerziteta u SAD-u. Osnovni princip predloženog algoritma je često restartovanje i biranje novog redosleda razmatranja Sudoku polja kao alternativa čekanju da se do rešenja dođe prvobitnim redosledom razmatranja. Na internet strani Prof. Gomes-a (http://www.cs.cornell.edu/gomes/SUDOKU/Sudoku.html) može se pronaći i zanimljivi program koji na primeru Sudokua dimenzija 9x9, 16x16, i 25x25 ilustruje efikasnost novo-otkrivenog algoritma.
Sudoku šampioni
Jana Tylova: Svetska Sudoku prvakinja
Zaljubljenici u Sudoku iz celoga sveta imali su priliku da se okušaju na prvom Svetskom Sudoku prvenstvu održanom u Italiji, marta 2006 godine (http://www.wsc2006.com/eng/index.php). Za titulu šampiona Sudokua borilo se 85 predstavnika iz više od 20 zemalja, a između ostalih je i Srbija i Crna Gora imala svoj tim. Naš takmičar Nikola Živanović je postigao veliki uspeh plasiravši se u finale. Prvo mesto pripalo je trideset jednogodišnjoj Jani Tylovoj iz Češke.
Ukoliko i sami želite da se okušate u Sudoku-u, evo i nekoliko linkova: http://www.dailysudoku.com
http://www.websudoku.com
Zarazio sam se sa ovom zezalicom, nedavno.. idelano za odrzavanje mozga u pokretu
Da li se iko oprobao u ovome?