Обхід конем шахової дошки

Як обійти конем шахову дошку, не побувавши ні на якому полі двічі і повернувшись у вихідну клітку?

Абсолютно заслужено вираз "хід конем" означає в українській мові дуже хитромудрий і нетривіальний задум. Ось і завдання обходу дошки є досить міцним горішком, на якому обламують зуби навіть деякі професіонали. Ні, звичайно, знайти якийсь один обхід не так складно. Наприклад, легко можна намалювати на папері маршрут обходу конем дошки 4x4, а потім розірвати 4 цих маршруту поблизу центру дошки і склеїти з них один маршрут. Є й інший відомий спосіб: спочатку обійти "облямівку" дошки шириною в дві клітини, а потім - центральні 16 клітин.

Але мене в цьому сюжеті цікавить (і завжди цікавило) нереалізації конкретного обходу, знайденого фактично вручну, а зовсім інше. Наприклад, нехай обхід вже розпочато - кінь вже побував на кількох клітинах. Чи можна завершити цей обхід? Якщо так, то як діяти? Очевидно, що тут завдання зовсім не залежить від конкретного розміру і навіть від форми дошки. Точно таку ж задачу можна поставити на зовсім довільному графі. Єдине, що нам тут потрібно від коня і дошки - це знати, які клітини для коня є "сусідніми", а які - ні.

От саме в цьому завданні повний перебір всіх варіантів недоступний навіть для нинішніх комп'ютерів, так що доводиться шукати інші шляхи. Власне, хороші ідеї давно відомі. Наприклад, відомо таке правило: кінь завжди повинен перескакувати на клітку, для якої кількість можливих ходів з неї є найменшим. А якщо таких клітин кілька? Однозначної рецепта, як бачите, немає ...

Тут навіть можна купити готове рішення-програму на Паскалі. Але цікавіше розібратися з алгоритмом самому.

Як Панов вирішує завдання наосліп - мнемонічний трюк!

Алгоритми дискретної математики для цього завдання - шамільтонов цикл і не тільки.

Правило, яке, мабуть, виправдовується на практиці, але ще не підтверджено теоретично полягає в наступному: щоразу ходимо конем туди, звідки він загрожує найменшому числу ще не пройдених клітин.

Інший спосіб полягає в знаходженні маршруту по половинці дошки, симетричному дублювання його і з'єднанні обох маршрутів.

Оригінальна правило, дає лінійний за часом алгоритм обходу дошки. було запропоновано Варнсдорф (Warnsdorff) в 1983 році.

Правило формулюється дуже просто: наступний хід коня потрібно робити на клітку, звідки існує найменша кількість можливих ходів. Якщо клітин з однаковою кількістю ходом кілька, то можна вибрати будь-яку.

На практиці це реалізується, наприклад, наступним чином. Перед кожним ходом коня обчислюється рейтинг найближчих доступних полів - полів, на яких кінь ще не був, і на які він може перейти за один хід. Рейтинг поля визначається числом найближчих доступних з нього полів. Чим менше рейтинг, тим він кращий. Потім робиться хід на поле з найменшим рейтингом (на будь-який з таких, якщо їх декілька), і так далі, поки є куди ходити.

Евристика завжди працює на дошках від 5x5 до 76x76 клітин, при великих розмірах дошки кінь може зайти в глухий кут. Крім того, що базується на правилі алгоритм не дає всіх можливих рішень (тобто шляхів коня): можна піти проти правила і все одно отримати задовольняє умові завдання обхід.

Існує лінійний алгоритм для дощок будь-якого розміру, який ділить дошку на менші частини, але, через велику кількість особливих випадків, він досить складний і не такий цікавий, як ця елегантна евристика.

Інший спосіб вирішення завдання, складається, очевидно, в переборі з відходом назад. Нижче дана ілюстрація підходу для дошки 8x8.

Використовуємо два одновимірних масиву row [64] і col [64] для зберігання відповідно номерів рядків і колонок, які кінь послідовно проходить по дошці.

Кінь, що знаходиться в позиції (i, j), може наступним ходом опинитися в клітинах з координатами (i-2, j + 1), (i-1, j + 2), (i + 1, j + 2), ( i + 2. j + 1), (i + 2. j-1), (i + 1, j-2), (i-1, j-2), (i-2, j-1). Зауважимо, що якщо кінь знаходиться поблизу краю дошки, то деякі ходи можуть викликати переміщення коня за її межі, що, звичайно ж, неприпустимо. Вісім можливих переміщень коня можуть бути задані у вигляді двох масивів ktmov1 [] і ktmov2 [], як продемонстровано в наступному фрагменті програми.

Виходячи з цього, кінь, що знаходиться в позиції (i, j) може переміститися в позицію (i + ktmov [k], j + ktmov2 [k]), де k - будь-яке значення з діапазону 0 - 7, вибираємо з умови , що кінь повинен залишитися на дошці. Отже, програма, яка реалізує переміщення коня відповідно до вищенаведених умов буде виглядати наступним чином:
int arr [8] [8], row [64], col [64];
int ktmov1 [8] = <-2, -1, 1, 2, 2, 1, -1, -2>;
int ktmov2 [8] = <1, 2, 2, 1, -1, -2, -2, -1>;

int i, j, move_num, d;

addknight () register int a, b, e;

/ * Помітити клітку як відвідану і запам'ятати координати клітини * /
arr [i] [j] = 1;
row [move_num] = i;
col [move_num] = j;
move_num ++;

/ * Перевірити 8 можливих переміщень коня * /
for (a = 0; a <= 7 ; a++ ) /* если все ходы сделаны, печатаем их */
if (move_num> = 64) writeboard ();
exit (0);
>

/ * Визначаємо колонку і рядок для наступного ходу * /
b = i + ktmov1 [a];
e = j + ktmov2 [a];

/ * Перевіряємо, що після виполененія ходу кінь залишається на шахівниці * /
if (b <0 || b> 7 || e <0 || e> 7)
continue;

/ * Перевіряємо, чи були ми вже в цій клітці * /
if (arr [b] [e] == 1)
continue;
i = b; j = e;
addknight ();
>

/ * Зменшити лічильник ходів і спробувати зробити наступний хід * /
move_num--;

/ * Звільняємо клітку, раніше зайняту конем * /
arr [row [move_num]] [col [move_num]] = 0;
move_num--; / * Пробуємо зробити наступний хід * /
i = row [move_num]; j = col [move_num];
move_num ++;
>

writeboard () int a;

clrscr ();
gotoxy (1, 10);
printf ( "Hit any key for next move");
gotoxy (1, 11);
for (a = 0; a <= 63 ; a++ ) if ( a % 8 == 0 )
printf ( "\ n");
printf ( "#");
>
for (a = 0; a lt; = 63; a ++) gotoxy (col [a] * 3 + 1, 12 + row [a]);
printf ( "% 3d", a + 1);
getch ();
>
>