Konjićev put

Konjićev put (engl. Knight's tour) je niz poteza figure konja na šahovskoj tabli, takvih da svako polje bude posećeno tačno jednom. Ako konj svoj put završi tačno na onom polju sa kog je krenuo (tako da može obiđe tablu istim poljima još jednom) kažemo da je put zatvoren, inače kažemo da je otvoren. Tačan broj otvorenih konjićevih puteva standardne 8 × 8 šahovske table još uvek je nepoznat.

U teoriji pronalaženje konjićevog puta je matematički problem, i često se zadaje studentima informatike kako bi napisali odgovarajući program koji pronalazi konjićev put. Različite varijante ovog problema uključuju i pronalaženje rešenja za table nestandardnih veličina, kao i rešenja za table koje nisu pravougaonog oblika.^[1]

Teorija[uredi | uredi izvor]

U teoriji pronalaženje konjićevog puta je primer mnogo opštijeg problema pronalaska Hamiltonovog puta u teoriji grafova. Problem pronalaženja zatvorenog konjićevog puta možemo postmatrati kao instancu problema pronalaženja Hamiltonovog ciklusa u grafu. Primetimo, ipak, da za razliku od rešenja za Hamiltonov put, rešenje za konjićev put možemo dobiti u linearnom vremenu.^[2]

Istorija[uredi | uredi izvor]

Konjićev put rešen od strane „Turka”, mašine za igranje šaha. Konkretno ovo rešenje je zatvoreno i primenljivo sa svakog početnog polja.

Najstariji pisani trag ovog problema datira još iz devetog veka. Indijski pesnik Rudrata u svojoj zbirci pesama „Kavialankara” koristio je niz šablona konjićevog puta na polovini šahovske table u poetskoj figuri zvanoj „turagapadabanda” ili „raspored u konjevim koracima”. Strofa se može čitati na isti način sleva nadesno i prateći konjićev put. Budući da je indijsko pismo korišćeno ovom prilikom slogovno, svaki slog može se posmatrati kao jedno polje na šahovskoj tabli.

से ना ली ली ली ना ना ना ली

ली ना ना ना ना ली ली ली ली

न ली ना ली ली ले ना ली ना

ली ली ली ना ना ना ना ना ली

se nā lī lī lī nā nā lī

lī nā nā nā nā lī lī lī

na lī nā lī le nā lī nā

lī lī lī nā nā nā nā lī

Na primer, prva linija se može čitati sleva nadesno ili krenući od prvog sloga do trećeg u drugom redu(2.3), pa zatim do sloga 1.5 i redom preko 2.7, 4.8, 3.6, 4.4, do 3.2.

Jedan od prvih matematičara koji je proučavao konjićev put bio je Leonard Ojler. Prvi postupak za pronalaženje konjićevog puta bilo je Vornsdorfovo pravilo, prvi put opisano 1823 od stane H. fon Vornsdorfa.

U šestoj igri svetskog prvenstva u šahu održanog 2010-e godine između Visvanatana Ananda i Veselina Topalova, primećeno je da je Anand napravio 13 uzastopnih poteza konjem(koristeći obe figure konja), a komentatori ovog duela našalili su se na njegov račun rekavši da on možda pokušava da reši problem konjićevog puta za vreme igre.

Broj zatvorenih puteva[uredi | uredi izvor]

Na 8 × 8 šahovsoj tabli postoji tačno 26.534.728,821,064 usmerenih konjićevih puteva. Broj neusmerenih puteva je polovina ovog broj budući da se svaki usmeren put može obići i u suprotnom smeru. Na 6h6 tabli broj neusmerenih zatvorenih konjićevih puteva je 9,862.

Koje table imaju put[uredi | uredi izvor]

Švenk je dokazao da za bilo koju m × n tablu gde je m manje ili jednako n, moguće pronaći zatvoren konjićev put osim u slučaju:

m i su oba neparna; n nije 1.
m = 1,2 ili 4; n nije 1.
m = 3 i n = 4,6 ili 8.

Kul i de Kurtins dokazali su da za svaku tablu pravougaonog oblika čija je manja dimenzija veća od 5, postoji (otvoren) konjićev put.

Pronalaženje puteva uz pomoć računara[uredi | uredi izvor]

Postoji veliki broj načina za pronalaženje konjićevog puta na tabli zadatih dimenzija pomoću računara. Neki od ovih metoda su algoritmi dok su drugi heuristike.

Algoritmi grube sile[uredi | uredi izvor]

Potraga za konjićevim putem primenom algoritama grube sile je nepraktičan za sve osim za table veoma malih dimenzija. Na primer na 8 × 8 šahovskoj tabli postoji približno 4×10⁵¹ nizova poteza, što je daleko iznad kapaciteta modernih računara.

Algoritmi tipa podeli pa vladaj[uredi | uredi izvor]

Deleći tablu na polja, zatim određivajući put za svaki od njih, i ponovo sklapajući tablu, možemo pronaći konjićev put na većini pravougaonih tabli u polinomijalnom vremenu.

Rešenja uz pomoć nervnih mreža[uredi | uredi izvor]

Problem konjićevog puta koristi se u implementaciji nervnih mreža. Mreže su napravljene tako što je svaki dozvoljeni potez konjem predstavljen kao nerv, a svakom nervu je inicijalno nasumično postavljena vrednost „aktivan” ili „neaktivan” (1 ili 0), sa 1 ukoliko je nerv deo krajnjeg rešenja. Svaki nerv ima funkciju stanja (opisanu ispod). Pri pokretanju mreže, svaki nerv može promeniti svoje stanje i izlaz na osnovu stanja i izlaza svojih suseda (koji su udaljeni tačno jedan potez od njega) i to prateći sledeća pravila:

U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)

V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{if}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{if}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{otherwise}},\end{array}}\right.

Gde $t$ predstavlja intervale vremena, $U(N_{i,j})$ je stanje nerva koji povezuje polje $i$ do polja $j$ , $V(N_{i,j})$ je izlaz nerva od $i$ do $j$ , i $G(N_{i,j})$ je skup suseda nerva.

Iako mreža može da divergira, u nekim slučajevima će konvergirati, i to kada nijedan nerv ne menja svoje stanje od $t$ do $t+1$ . Kada mreža konvergira pronađen je ili konjićev put, ili serija od dva ili više ciklusa na tabli.

Vornsdorfovo pravilo[uredi | uredi izvor]

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Grafička reprezentacija Vornsdorfovog pravila. Svako polje sadrži broj mogućih sledećih poteza. U ovom slučaju pravilo nam kaže da treba ići na polje sa najmanjim brojem na njemu, odnosno 2.

Vornsdorfovo pravilo je heuristika za pronalaženje konjićevog puta. Pomeramo konja na ono polje sa kog bi imali najmanje izbora za sledeći potez. Prilikom računanja polja za sledeći potez, ne računamo polja koja smo već posetili. Naravno, moguće je da za sledeći potez imamo dva ili više polja sa istim brojem izbora za sledeći potez, i postoje različiti metodi za rešavanje ovakvih slučajeva, uključujući Polov metod ili metod Skvirela i Kula.

Ovo pravilo takođe može biti uopšteno na bilo koji graf. U kontekstu teorije grafova, svaki potez je napravljen ka čvoru sa najmanjim izlaznim stepenom. Iako je problem Hamiltonovog puta NP-težak u opštem slučaju, u praksi se pokazalo da ova heuristika daje rešenje u linearnom vremenu za veliki broj grafova, a konjićev put je jedan specijalnih slučajeva ovog problema.

Ova heuristika prvi put je opisana u „Des Rösselsprungs einfachste und allgemeinste Lösung” od strane H. fon Vornsdorfa 1823. godine. Program koji pronalazi konjićev put za bilo koje početno polje na šahovskoj tabli koristeći Vornsdorfovo pravilo može se pronaći u knjizi „Century/Acorn User Book of Computer Puzzles”.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ H. M. Deitel, P. J. Deitel. „Java How To Program Fifth Edition.” Prentice Hall, Upper Saddle River, New Jersey, pp. 326—328. 2003.
^ Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). „Solution of the Knight's Hamiltonian Path Problem on Chessboards”. Discrete Applied Mathematics. 50 (2): 125—134. doi:10.1016/0166-218X(92)00170-Q.

Spoljašnje veze[uredi | uredi izvor]

Warnsdorff's Rule and its efficiency from Warnsdorff's Rule Web Page
Thomasson, Dan. „The knight's tour”. Arhivirano iz originala 19. decembar 2005. g. Pristupljeno 29. maj 2013.
Knight's tour notes
Knight's Tour Flash Game
warnsdorff.com — Page devoted to Warnsdorff's Rule

[1] H. M. Deitel, P. J. Deitel. „Java How To Program Fifth Edition.” Prentice Hall, Upper Saddle River, New Jersey, pp. 326—328. 2003.

[2] Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). „Solution of the Knight's Hamiltonian Path Problem on Chessboards”. Discrete Applied Mathematics. 50 (2): 125—134. doi:10.1016/0166-218X(92)00170-Q.

[1]

[2]