Pa ako znas sta je pencil metoda onda je lako. Ali ajde ukratko :)
Red, kolona, kvadrat cemo zvati oblik jednim imenom za nadalje, isto kada kazem broj se ne nalazi u obliku znaci ne nalazi se u nekom redu, koloni ili kvadratu i naglasicemo ako je potrebno (da ne zalazim dublje u formalizam).
Na svim nepopunjenim poljima napises mali broj od 1 do 9 i to samo one brojeve koji mogu da budu tu kao resenje. Mozda nije lose da za sva nepopunjena polja stavis da mogu svi od 1 do 9, pa onda ides redom po oblicima i skidas ono sto je pronadjeno. Na primer ako u nekom redu je vec pronadjena 1 onda prezvrsljas (obrises) tu malu 1-cu.
Naravno odmah mozes predpostaviti ako na nekom polju imas samo jedan mali broj, taj broj jedino moze da bude tu. To je pocetna heuristika.
Ajmo dalje, ako u nekom obliku imas samo jedan mali broj x onda bas na tom mestu mora da bude x. Hoce reci ako na primer u nekoj koloni koja je cela neotrkivena samo na jednom mestu pise mala cetvroka, na tom polju je 4.
Naravno kada pronadjes neki broj (to jest zakljucis da je tu), onda brises iz svih oblika koje sadrze to polje sve pojave tog pronadjenog broja. I ovo je valjda jasno.
To su vec dve osnovne heuristike, u ovom izlaganju cu navesti jos jednu koja je veoma laka za implementaciju. Ispricacu za slucaj kada posmatramo dva broja :).
Dakle ako u nekom obliku na dva mesta mogu da budu samo brojevi x i y, x i y se ne mogu nalaziti nigde vise. Primer: u nekoj koloni imamo sledece kombinacije:
na mestu 1: (2 3 5 6)
na mestu 4: (2 3)
na mestu 5: (3 7)
na mestu 6: (2 3)
Sta mozemo zakljuciti: da mestima 4 i 6 su brojevi 2 i 3 u nekoj od kombinacija (2 3 ili 3 2). To jest 2 i 3 u toj koloni ne mogu biti na ni jednom drugom mestu (jos malo ubedjivanja: ako je 2 na mesutu 4 onda je na mestu 6 3, i obrnuto ako je na mestu 4 3 onda je na mestu 6 2; 2 i 3 ne mogu biti nigde drugde.
Zakljucak posle ovoga (2 i 3 su taj spominjani naked pair):
na mestu 1: (5 6)
na mestu 4: (2 3)
na mestu 5: pronasli smo 7
na mestu 6: (2 3)
Slicno moze i za trojku brojeva, ali na tri mesta naravno :).
Za isprobavanje ovoga preprucujem neki program koji prikazuje pencile, recimo:
http://www.divingforbananas.com/sudoku/
Recimo onaj gornji novo moze da se resi koristeci samo ove 3 heuristike:
- jedinstven u polju
- jedinstven u obliku
- naked pair
Naravno naked pair je dosta tesko u glavi realizovati, ali svakako lici na igru memorije :).
Ima jos nekoliko heuristika, tipa preseci, krilo, leptiric, remote pairs. Ja za sada volim da izucavam samo one heuristike koje se ne svode na backtracing :).
Ajde ukratko:
-Presek: ako se u obliku A nalazi neki broj samo u onim poljima koji pripadaju i nekom drugom obliku B, onda iz ostalih polja oblika B mozemo taj broj eliminisati.
-krilo: ako se neki broj nalazi samo po dva puta u dva reda i to na istom mestu, onda mozemo u kolonama na tom istom mestu da eliminisemo taj broj.
-leptiric: slicno kao krilo, ali sa malo vise polja u igri
-remote pair, isto slicno, ali se prave lanci iskljucivanja.
Eto, ima dosta za izucavanje :)
Citat:
aleksandrin: ala vi imate viska vremena
Pa mozda ja to ipak smatram investiranjem u svoj mozak, nekako mora da se bilduje i mozak, zar ne ?
CHUPCKO
sudoku, za koliko
Registrovani: 1 ( vjova )
:)
