"GENERIRAJ NOVI" stvara sudoku zadatak sa odabranim brojem poznatih polja. Nakon toga se sudoku može
ručno rješavati: prvo se bira mjesto u tablici, pa onda znamenka (ili praznina) za upis na to mjesto.
"UNOS NOVOGA" omogućuje ručno zadavanja sudoku-a unosom znamenki na gore opisani način.
"KRAJ ZADAVANJA" prekida ručno zadavanje sudoku-a. Ako je uneseni zadatak ispravan, prelazi se u mod
ručnog rješavanja. Naravno, moguće je i automatsko rješavanje.
Tijekom ručnog rješavanja mogu se koristiti i tipke sa simbolima: " < " je "Undo" (poništi prethodni unos znamenke, ili više njih, korak po korak unazad) " > " je "Redo" (poništi Undo, ili više njih, korak po korak)
"UNIQUE?" ispituje da li trenutni sadržaj tablice ima jedno ili više mogućih rješenja. Ova funkcija
je korisna za provjeru ispravnosti kada se ručno unese sudoku zadatak iz neke druge publikacije.
"RIJEŠI SUDOKU" predaje trenutni sadržaj tablice algoritmu za automatsko rješavanje.
"PONIŠTI RJEŠENJE" vraća u tablicu stanje kakvo je bilo prije automatskog rješavanja.
Simbol diskete (u gornjem lijevom uglu) omogućuje da u nekoj fazi rješavanja snimite trenutno stanje. "Undo"
i "Redo" koraci se ne snimaju. Nekom drugom prilikom, u fazi zadavanja, navedeni simbol vraća u tablicu
snimljeno stanje, pa se može nastaviti sa rješavanjem.
Link iz podnaslova naizmjenično zadaje 4 pred-definirana zadatka: 2 koji na internetu
slove kao najteži (ljudima) i 2 koji su ciljano napravljeni da zbune BACKTRACKING algoritam. Modificirani
algoritam tog tipa ovdje koristimo za automatsko rješavanje.
Prilikom ručnog rješavanja može se koristiti prikaz "legalnih" znamenki i/ili opomene kod unosa ilegalnih.
Nažalost, to umanjuje zanimljivost.
U bilo kojem trenutku stanje tablice može biti poslano na štampanje, npr. za rješavanje na papiru.
NAPOMENA:
Ako vam se učini da je rješavanje ili generiranje zapelo, budite strpljivi. Rezultat će sigurno biti
prikazan. Radi se o tome da neki preglednici tijekom intenzivnog kalkuliranja ne prikazuju promjene na ekranu.
Zato se poruka "ČEKAJTE ..." ponekad ne vidi.
OBJAŠNJENJA
ŠTO JE "BACKTRACKING" ALGORITAM:
To je, u stvari, rješavanje sirovom snagom: Pokušava se upisati svaka, prema pravilima dopuštena kombijacija,
sve dok se ne dođe do rješenja. Počevši od prvog slobodnog polja upisuje se prva dopuštena znamenka, uz
pretpostavku da je točna. U sljedeće polje upisuje se sljedeća moguća znamenka, i tako sve dok se ne dođe u
situaciju da se nijedna znamenka ne smije upisati u sljedeće slobodno polje. Tada se poništi zadnja, prethodno
upisana znamenka, zamijeni se prvom sljedećom dopuštenom i pokušava se ponovo. Ako ni jedna ne uspije, vraća
se još korak unatrag, mijenja se ta pret-prethodna znamenka i pokušava se napredovati ...
Kako mogućih kombinacija ima strahovito mnogo, takvo rješavanje bi moglo potrajati satima ako je sudoku
konstruiran tako da "kontrira" logici rješavanja.
Da bi se rješenje dobilo u razumnom roku, u ovaj algoritam je unesen kompromis: ograničen je na 1 milion
koraka, ali mu je dodana mogućnost drugačijeg pristupa. - Ako sudoku nije riješen u milion koraka, pristupa mu
se iz drugog kuta: ležeći. S ljudskog stanovišta to nema nekog smisla, ali računalo je sretno - sudoku je
ostao isti, ali je redosljed rješavanja drugačiji.
Ako ni tako ne uspije u milion koraka, sudoku se okreće "naglavačke". Pa zrcalno, pa dijagonalno ...
U najvećem broju slučajeva sudoku će biti uspješno riješen. Ipak, postoji mala vjerojatnost da milion
koraka ne bude dovoljno ni u jednoj orjentaciji. To se može desiti kada sudoku ima malo poznatih polja i još
je pri tome pažljivo konstruiran.
Na kraju se prikazuje broj koraka do rješenja, a u zagradi će biti broj "drugačijih pristupa" koje je
obradio da bi riješio zadani sudoku.
GENERIRANJE SUDOKU ZADATKA:
Najprimitivniji način je niz koraka koji, počevši od prazne tablice, dodaju nove znamenke. Lokacije se biraju
nasumično, znamenka također i onda se provjerava da li je sve po pravilima i da li je sudoku rješiv. Kada se
dosegne željena popunjenost, provjerava se da li je rješenje jedinstveno (nazovimo to svojstvo UNIQUE). Ako
nije, sve iz početka.
I tu nastupa problem: Kada je popunjenost veća od 30-tak polja, algoritam prilično brzo pronađe UNIQUE sudoku
(najčešće unutar 20-tak pokušaja). Ali, ako je tražena popunjenost manja, takvi su sve rjeđi, pa ih je i teže
pronaći - a to traje.
Da bi se složio UNIQUE sudoku, potrebno je imati barem 17 poznatih polja. Traženje takvog u realnom vremenu
gotovo da nije moguće.
SITNE PREVARE:
Ako na internetu pogledamo stranice koje nude sudoku-e teških, ekstremnih, "evil" i sličnih razina težine
možemo uočiti da se sudoku sa npr. 17 zadanih polja pojavljuje trenutno. Pa kako je to moguće?
Ne, nije u pitanju baza podataka sa pripremljenim zadacima, nego manipulacija nad jednim jedinim "uzorkom"!
Uzmimo bilo koji UNIQUE sudoku. "Šifrirajmo" ga na onaj stari, dječji način - zamjenom znamenki po ključu:
- Mijenjamo sve jedinice u 9, sve dvojke u 8, sve trojke u 7, ...., sve osmice u 2 i sve devetke u 1
(ili bilo kojim drugačije pomiješanim nizom tih znamenki). Dobili smo novi sudoku, sa istim rasporedom ali
sa drugim znamenkama, u suštini isti sudoku.
- Okrenimo ga u "ležeći" položaj. Izgleda potpuno različito od originala, ali je i dalje u suštini isti.
- Prepišimo ga zrcalno: prvi redak postaje zadnji, drugi postaje predzadnji itd. I dalje je isti, a različit.
- Možemo čak mijenjati raspored cijelih redaka unutar tro-rednih skupina: zamjena mjesta 4. i 5. retka ne
narušava ni jedno pravilo, a ni svojstvo rješivosti ili UNIQUE.
- Možemo zamijeniti i cijele tro-redne skupine: Prva 3 retka stavimo na mjesto četvrtog, petog i šestog, a njih
na mjesto prvog, drugog i trećeg. Isto važi i po stupcima.
Tako radi i ovaj generator ako se traži popunjenost od 17, 20 ili 25 poznatih polja. Poruka "ČEKAJTE ..."
samo ostavlja dojam da stvarno nešto radi.
Ako se traži popunjenost od 26 polja ili više, generator stvarno traži novi raspored, pa će i poruka
"ČEKAJTE ..." trajati nešto duže.