Коњићев пут

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

У теорији проналажење коњићевог пута је математички проблем, и често се задаје студентима информатике како би написали одговарајући програм који проналази коњићев пут. Различите варијанте овог проблема укључују и проналажење решења за табле нестандардних величина, као и решења за табле које нису правоугаоног облика.^[1]

Теорија

У теорији проналажење коњићевог пута је пример много општијег проблема проналаска Хамилтоновог пута у теорији графова. Проблем проналажења затвореног коњићевог пута можемо постматрати као инстанцу проблема проналажења Хамилтоновог циклуса у графу. Приметимо, ипак, да за разлику од решења за Хамилтонов пут, решење за коњићев пут можемо добити у линеарном времену.^[2]

Историја

Коњићев пут решен од стране „Турка”, машине за играње шаха. Конкретно ово решење је затворено и применљиво са сваког почетног поља.

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

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

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

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

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

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ī

На пример, прва линија се може читати слева надесно или кренући од првог слога до трећег у другом реду(2.3), па затим до слога 1.5 и редом преко 2.7, 4.8, 3.6, 4.4, до 3.2.

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

У шестој игри светског првенства у шаху одржаног 2010-е године између Висванатана Ананда и Веселина Топалова, примећено је да је Ананд направио 13 узастопних потеза коњем(користећи обе фигуре коња), а коментатори овог дуела нашалили су се на његов рачун рекавши да он можда покушава да реши проблем коњићевог пута за време игре.

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

На 8 × 8 шаховсој табли постоји тачно 26.534.728,821,064 усмерених коњићевих путева. Број неусмерених путева је половина овог број будући да се сваки усмерен пут може обићи и у супротном смеру. На 6х6 табли број неусмерених затворених коњићевих путева је 9,862.

Које табле имају пут

Швенк је доказао да за било коју m × n таблу где је m мање или једнако n, могуће пронаћи затворен коњићев пут осим у случају:

m и су оба непарна; n није 1.
m = 1,2 или 4; n није 1.
m = 3 и n = 4,6 или 8.

Кул и де Куртинс доказали су да за сваку таблу правоугаоног облика чија је мања димензија већа од 5, постоји (отворен) коњићев пут.

Проналажење путева уз помоћ рачунара

Постоји велики број начина за проналажење коњићевог пута на табли задатих димензија помоћу рачунара. Неки од ових метода су алгоритми док су други хеуристике.

Алгоритми грубе силе

Потрага за коњићевим путем применом алгоритама грубе силе је непрактичан за све осим за табле веома малих димензија. На пример на 8 × 8 шаховској табли постоји приближно 4×10⁵¹ низова потеза, што је далеко изнад капацитета модерних рачунара.

Алгоритми типа подели па владај

Делећи таблу на поља, затим одређивајући пут за сваки од њих, и поново склапајући таблу, можемо пронаћи коњићев пут на већини правоугаоних табли у полиномијалном времену.

Решења уз помоћ нервних мрежа

Проблем коњићевог пута користи се у имплементацији нервних мрежа. Мреже су направљене тако што је сваки дозвољени потез коњем представљен као нерв, а сваком нерву је иницијално насумично постављена вредност „активан” или „неактиван” (1 или 0), са 1 уколико је нерв део крајњег решења. Сваки нерв има функцију стања (описану испод). При покретању мреже, сваки нерв може променити своје стање и излаз на основу стања и излаза својих суседа (који су удаљени тачно један потез од њега) и то пратећи следећа правила:

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.

Где $t$ представља интервале времена, $U(N_{i,j})$ је стање нерва који повезује поље $i$ до поља $j$ , $V(N_{i,j})$ је излаз нерва од $i$ до $j$ , и $G(N_{i,j})$ је скуп суседа нерва.

Иако мрежа може да дивергира, у неким случајевима ће конвергирати, и то када ниједан нерв не мења своје стање од $t$ до $t+1$ . Када мрежа конвергира пронађен је или коњићев пут, или серија од два или више циклуса на табли.

Ворнсдорфово правило

	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

Графичка репрезентација Ворнсдорфовог правила. Свако поље садржи број могућих следећих потеза. У овом случају правило нам каже да треба ићи на поље са најмањим бројем на њему, односно 2.

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

Ово правило такође може бити уопштено на било који граф. У контексту теорије графова, сваки потез је направљен ка чвору са најмањим излазним степеном. Иако је проблем Хамилтоновог пута НП-тежак у општем случају, у пракси се показало да ова хеуристика даје решење у линеарном времену за велики број графова, а коњићев пут је један специјалних случајева овог проблема.

Ова хеуристика први пут је описана у „Des Rösselsprungs einfachste und allgemeinste Lösung” од стране Х. фон Ворнсдорфа 1823. године. Програм који проналази коњићев пут за било које почетно поље на шаховској табли користећи Ворнсдорфово правило може се пронаћи у књизи „Century/Acorn User Book of Computer Puzzles”.

Види још

Референце

^ 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.

Спољашње везе

Warnsdorff's Rule and its efficiency from Warnsdorff's Rule Web Page
Thomasson, Dan. „The knight's tour”. Архивирано из оригинала 19. децембар 2005. г. Приступљено 29. мај 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]