Коњићев пут

Из Википедије, слободне енциклопедије
Отворен коњићев пут на шаховској табли.
Анимација коњићевог пута на 5х5 табли.

Коњићев пут (енгл. 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, могуће пронаћи затворен коњићев пут осим у случају:

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

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

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

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

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

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

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

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

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

Проблем коњићевог пута користи се у имплементацији нервних мрежа. Мреже су направљене тако што је сваки дозвољени потез коњем представљен као нерв, а сваком нерву је иницијално насумично постављена вредност "активан" или "неактиван" (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. Када мрежа конвергира пронађен је или коњићев пут, или серија од два или више циклуса на табли.

Ворнсдорфово правило[уреди]

Chess zhor 26 cyr.png
Chess zver 26.png
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.png
Chess zhor 26 cyr.png
Графичка репрезентација Ворнсдорфовог правила. Свако поље садржи број могућих следећих потеза. У овом случају правило нам каже да требамо ићи на поље са најмањим бројем на њему, односно 2.

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

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

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

Види још[уреди]

Референце[уреди]

  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. 

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Коњићев пут