Історія задачі про обхід коня
Задачі про обхід коня близько тисячі років: перші записані розвʼязки — з IX століття, а звати її кінцем не квапляться й досі.
IX століття: перші записані обходи
Найдавніші відомі розвʼязки лишили аль-Адлі ар-Румі в Багдаді й, приблизно тоді ж, Рудрата в Кашмірі. Обидва працювали з дошкою 8×8 і обидва записали готові обходи, а не спосіб їх шукати.
Рудрата зробив це у віршах: його обхід — це вірш, у якому склади розкладені по клітинках так, що прочитати їх можна і рядками, і ходом коня.
1759: Ейлер
Леонард Ейлер узявся за задачу як за математичну, а не як за головоломку, і саме після нього вона перестала бути шаховою цікавинкою. Його підхід — добудовувати незавершений обхід до повного — досі викладають.
Сьогодні задачу про обхід коня наводять як хрестоматійний приклад гамільтонового шляху в графі, де вершини це клітинки, а ребра — можливі стрибки.
1823: правило Варнсдорфа
Х. К. фон Варнсдорф запропонував правило, яке звучить майже надто просто: щоразу йти на ту клітинку, з якої далі лишиться найменше ходів.
На звичайних дошках це дає повний обхід майже завжди й майже миттєво. Саме ці числа гра друкує на клітинках у режимі «Учень» — не як підказку, куди ходити, а як спосіб побачити дошку так, як її бачить розвʼязувач.
1991: теорема Швенка
Аллен Швенк описав, які саме прямокутні дошки m×n обхід мають, а які ні. Це відповідь на питання, з якого починається будь-яка реалізація: чи має сенс шукати взагалі.
У грі це видно двома способами. Дошки починаються з 6×6, бо менші або не мають обходу, або надто малі. А на непарній дошці половина клітинок гасне до першого ходу — з них обхід не сходиться за кольоровим підрахунком.
Хід конем · Leap