шахматен кон

Терминът шахматен кон има няколко значения:

лека фигура от играта шахмат - правилния ход за местене изисква преместване на празно поле от текущата позиция под форма на буква "Г";

алгоритъм за описване възможните ходове на шахматния код от дадено поле;

логическа игра изискваща преминаване, без повторение, през всички полета на шахматната дъска спазвайки изискванията за ход на шахматен кон.

Логическата задача шахматен кон има множество имена: Knight's tour, обиколката на коня, ход на шахматен кон, задача за кон и шахматна дъска, разходка на шахматен кон.. И естествено има множество решения, но не безкрайно много - перефразиран цитат на Ойлер. Както и при логическата задача шахматни царици и тук е възможно едно правилно решение да се мултиплицира.

Най-често срещан вариант за избор на начална позиция е клетка от външния контур на шахматната дъска. Съществува отделен алгоритъм използващ произволно избрано начално поле.

Стратегиите за обхождане могат да бъдат условно групирани:

разделяне на шахматна дъска на 4 равни части по вертикала/хоризонтала, избор на начална част за приоритено обхождане;

разделяне на шахматна дъска на 2 равни части по вертикала/хоризонтала, избор на начална част за приоритетно обхождане;

обхождане по спирала с избрана посока;

от няколкото възможни хода се избира имащия повече варианти за продължение.

Това са правилата, към които играчът би трябвало да се придържа, но действителността е малко по-различна. Избраната посока често трябва да се сменя, във всяко от описаните решения има няколко момента с единствен възможен ход.

Избраният подход е мултиплициране на вече открито вярно решение.

Ойлер споменава за варианти на решение, в които началната и крайната позиция са на разстояние 1 конски ход. Години след това Волфганг фон Кемпелен  със своята фалшива машина Турчина използва този подход.

разстояние между начална и крайна позиция 1 ход на шахматен кон

Изборът на който и да е от двата варианта дава възможност произволно поле да бъде обявено за начално и при спазване на описаната последователност да се обходи шахматната дъска без повтаряне на полета.

Възможни са 128 варианта = 2 посоки на обхождане х 64 възможни начални позиции.

В десния вариант 13-тата позиция е обявена за 1-ва и е сменена посоката.

базов вариант модификация

12, 17, 26, 31, 10, 19, 24, 33; 02, 11, 16, 25, 04, 09, 18, 23;

27, 30, 11, 18, 25, 32, 07, 20; 15, 28, 03, 10, 17, 24, 05, 08;

16, 13, 28, 09, 04, 21, 34, 23; 12, 01, 14, 31, 26, 07, 22, 19;

29, 54, 37, 14, 35, 08, 47, 06; 29, 52, 27, 64, 21, 62, 45, 06;

38, 15, 40, 03, 46, 05, 22, 61; 38, 13, 30, 53, 32, 59, 20, 61;

55, 02, 53, 36, 41, 60, 45, 48; 51, 54, 39, 58, 63, 46, 33, 44;

52, 39, 64, 57, 50, 43, 62, 59; 40, 37, 56, 49, 42, 35, 60, 47;

01, 56, 51, 42, 63, 58, 49, 44; 55, 50, 41, 36, 57, 48, 43, 34;

При обхождане на шахматната дъска се ползва спирала с променлива посока по външния контур.

Изборът на един от следващите алгоритми за мултиплициране на вярно решение се влияе от базовия вариант.

разстояние между начална и крайна позиция >1 ход на шахматен кон

Ограниченията са значително повече за сметка на възможния брой варианти.

В десния вариант са разменени местата на начална - крайна позиция и е сменна посоката.

базов вариант модификация

30, 11, 24, 45, 32, 09, 22, 47; 35, 54, 41, 20, 33, 56, 43, 18;

25, 42, 31, 10, 23, 46, 33, 08; 40, 23, 34, 55, 42, 19, 32, 57;

12, 29, 44, 55, 60, 57, 48, 21; 53, 36, 21, 10, 05, 08, 17, 44;

43, 26, 41, 58, 63, 54, 07, 34; 22, 39, 24, 07, 02, 11, 58, 31;

40, 13, 28, 61, 56, 59, 20, 49; 25, 52, 37, 04, 09, 06, 45, 16;

27, 02, 15, 64, 53, 62, 35, 06; 38, 63, 50, 01, 12, 03, 30, 59;

14, 39, 52, 17, 04, 37, 50, 19; 51, 26, 13, 48, 61, 28, 15, 46;

01, 16, 03, 38, 51, 18, 05, 36; 64, 49, 62, 27, 14, 47, 60, 29;

прилагане на (вертикална) симетрия спрямо средата

базов вариант модификация

22, 17, 08, 03, 24, 15, 10, 01 33, 42, 47, 56, 35, 40, 49, 54

07, 04, 23, 16, 09, 02, 27, 14 46, 59, 34, 41, 48, 55, 36, 39

18, 21, 06, 25, 30, 13, 64, 11 43, 32, 45, 62, 57, 38, 53, 50

05, 44, 61, 20, 63, 26, 51, 28 60, 19, 58, 31, 52, 29, 12, 37

60, 19, 58, 31, 52, 29, 12, 37 05, 44, 61, 20, 63, 26, 51, 28

43, 32, 45, 62, 57, 38, 53, 50 18, 21, 06, 25, 30, 13, 64, 11

46, 59, 34, 41, 48, 55, 36, 39 07, 04, 23, 16, 09, 02, 27, 14

33, 42, 47, 56, 35, 40, 49, 54 22, 17, 08, 03, 24, 15, 10, 01

Със същия успех може да се приложи вертикална симетрия или по диагонал.

обръщане на 90⁰ по часовата стрелка

базов вариант модификация

30, 39, 18, 05, 32, 37, 20, 07; 13, 42, 27, 54, 15, 40, 17, 30;

17, 04, 31, 38, 19, 06, 33, 36; 26, 53, 14, 41, 02, 29, 04, 39;

40, 29, 16, 03, 62, 35, 08, 21; 43, 12, 55, 28, 61, 16, 31, 18;

15, 02, 61, 64, 59, 50, 57, 34; 52, 25, 60, 01, 64, 03, 38, 05;

54, 41, 28, 01, 56, 63, 22, 09; 11, 44, 51, 56, 59, 62, 19, 32;

27, 14, 55, 60, 51, 58, 49, 46; 24, 47, 58, 63, 50, 35, 06, 37;

42, 53, 12, 25, 44, 47, 10, 23; 45, 10, 49, 22, 57, 08, 33, 20;

13, 26, 43, 52, 11, 24, 45, 48; 48, 23, 46, 09, 34, 21, 36, 07;

Броят на възможните верни решения е голям, но много по-малък от броя на възможните грешни решения. Интересна задача е невъзможност да се запълни само последното поле.

неудачен ход на шахматен кон

Вариант с незапълнено последно поле.

17, 48, 31, 46, 15, 44, 29, 42;

32, 01, 16, 55, 30, 41, 14, 57;

49, 18, 47, 40, 45, 56, 43, 28;

02, 33, 54, 63, ?? , 39, 58, 13;

19, 50, 21, 34, 59, 08, 27, 38;

22, 03, 60, 53, 62, 37, 12, 09;

51, 20, 05, 24, 35, 10, 07, 26;

04, 23, 52, 61, 06, 25, 36, 11;

В приложението реализиращо логическата игра шахматен кон има вградени описания за няколко различни верни последователности.

Реализирани са следните функции:

автоматично генериране на оцветена таблица илюстрираща шахматна дъска;

автоматично показване на допустим ход;

възможност за посочване на позволено незаето място на върху шахматната дъска;

възможност за връщане назад 1 или повече хода;

възможност за бързо показване последователните верни ходове на шахматния кон от предварително избрано реализирано решение;

възможност за нова игра.

Съществуват публикации за решаване задачата шахматен кон чрез прилагане на други алгоритми като: динамично оптимиране, търсене с връщане назад, разделяй и владей. Задачата е ресурсоемка и времето за получаване на решение, при имплементиране на някой от изброените алгоритми, чувствително се влияе от избраната начална позиция. В случая (за бъдещия проект) се предлага константен масив - разход на памет с цел увеличаване на скоростта.

Други шахматни задачи като ход на царицата, ход на коня, ход на топа са разгледани в сайта рекурсия и итерация.

Разгледайте използваните алгоритми в други реализирани примерни проекти. Потърсете допълнителен материал за: търси числото, игра с логическа колона, обиколка в кръг.