Sudoku osvaja svet

[HLEBmaster]

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?

[valter]

-Javicu ti sutra

[ruzica]

ja sam malo zavisna od sudokua...

[Mish]

Ja sam već navučena na sudoku. Posebno je dobar za predah na poslu (teško da će me neko prokužiti da li mozgam o poslu ili samo rešavam sudoku).

[HLEBmaster]

Ih na poslu spas S obzirom da moram da chekam po nekad i vishe sati da komp neshto "iskompresuje" ili "izexportuje" sudoku mi dodje ko bombona. Nego pri ruci mi je obichno onaj u "24 chasa" besplatnim novinama... a tamo i inache po nekad vrvi od greshaka i gluposti, pa i sudoku po nekad ne mozzesh da reshish ili je sjeban jer se nadju po dve devetke u istom redu itd..

[vlado]

Postoje i novine "Sudoku" Iz njih sam i cuo za igru, koja mi se jako dopala, al' jebote mnoogo je teska. Sad je vec ima na Internetu -> zarazio sam se

[Bloo]

Joj, turio sam sudoku na mobilni i sad sam poceo da krisom pikam na poslu... Jednom su me navatali kako blejim dva sata u telefon pa sam poceo da se krijem kojekuda samo da na miru resim bar dve. Imam fazon da se zakljucham u wc na pola sata i tamo se izigram (mislim na sudoku) a kad izadjem niko me ne pita sta sam radio u wc-u pola sata da ne bi dobio malo pogrdan odgovor (naglas)

[HLEBmaster]

? jel moze to na SEriksonu da se sigra? I di si je nashao?

[1oredz3]

Volim sudoku!
Ponekad se zanesem, pa uz sudoku provedem i nekoliko sati!

[makilli]

I ja sam se poprilično navukla,ponekad se zablentavim na netu i po par sati...