Коњићев пут — разлика између измена

 

'''Коњићев пут''' ({{jez-eng|Knight's tour}}) је низ потеза фигуре коња на шаховској табли, таквих да свако поље буде посећено тачно једном. Ако коњ свој пут заврши тачно на оном пољу са ког је кренуо (тако да може обиђе таблу истим пољима још једном) кажемо да је пут затворен, иначе кажемо да је отворен. Тачан број отворених коњићевих путева стандардне 8 × 8 шаховске табле још увек је непознат.

 

== Теорија ==

 

У теорији проналажење коњићевог пута је пример много општијег проблема проналаска Хамилтоновог пута у теорији графова. Проблем проналажења затвореног коњићевог пута можемо постматрати као инстанцу проблема проналажења Хамилтоновог циклуса у графу. Приметимо, ипак, да за разлику од решења за Хамилтонов пут, решење за коњићев пут можемо добити у линеарном времену.<ref>{{Cite journal |first=A. |last=Conrad|first2=T. |last2=Hindrichs|first3=H. |last3=Morsy|lastauthoramp=yes |first4=I. |last4=Wegener|title=Solution of the Knight's Hamiltonian Path Problem on Chessboards |journal=Discrete Applied Mathematics |volume=50 |issue=2 |pages=125–134 |year=1994|doi=10.1016/0166-218X(92)00170-Q }}</ref>

{{clear}}

== Историја ==

 

Најстарији писани траг овог проблема датира још из деветог века. Индијски песник Рудрата у својој збирци песама "Кавиаланкара" користио је низ шаблона коњићевог пута на половини шаховске табле у поетској фигури званој "турагападабанда" или "распоред у коњевим корацима“. Строфа се може читати на исти начин с лева на десно и пратећи коњићев пут. Будући да је индијско писмо коришћено овом приликом слоговно, сваки слог може се посматрати као једно поље на шаховској табли.

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

 

 

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

 

 

Један од првих математичара који је проучавао коњићев пут био је Леонард Ојлер. Први поступак за проналажење коњићевог пута било је Ворнсдорфово правило, први пут описано 1823 од стане Х. фон Ворнсдорфа.

== Број затворених путева ==

 

је 9,862.