Правило Варнсдорфа
Back Home Up Next

В 1823 году Варнсдорф в брошюре “Простейшее и наиболее общее решение задачи о ходе коня” предложил следующее правило обхода доски размером 8´8.

На каждом ходу ставь коня на такое поле, из которого можно совершить наименьшее число ходов на еще не пройденные поля. Если таких полей несколько, разрешается выбирать любое из них.

На практике это правило легко позволяет строить обходы доски, хотя долгое время не было известно, справедливо ли оно. Опровержение правила Варнсдорфа приведено в [29, c.28-29], где для любого исходного поля доски указаны контрпримеры, построенные с помощью ЭВМ “Проминь-2”. Иными словами, с какого бы поля конь ни начал движение, следуя правилу Варнсдорфа, его можно завести в тупик до полного обхода доски.

Добавлением дополнительных ограничений к правилу Варнсдорфа можно получать те или иные алгоритмы перемещения коня по доске (возможно, и не приводящие к её обходу). Делать это можно фиксированием конкретного вида матрицы приращений D, используемой для получения кандидатов на очередной ход и правила однозначного выбора хода в неопределенных ситуациях. Как мы уже отмечали, зафиксировать D можно 40320 способами. На рисунке 3 указан один из них. При наличии нескольких допустимых ходов условимся выбирать тот из них, который сформирован с помощью самого левого столбца D. При фиксированной матрице D соответствующий алгоритм перемещения коня назовем D-алгоритмом.

Рис. 3. Схема предпочтения ходов в неопределенных ситуациях

адача 5. Обход доски конем D-алгоритмом. Пусть D зафиксировано и на шахматной доске размером n´n в позиции (x, y) находится конь. Составить рекурсивную программу-функцию, находящую D-алгоритмом обход доски конем, если он существует. При отсутствии обхода должна быть выдана “тупиковая позиция” - матрица-доска с уже зафиксированным неполным обходом.

Решение. Функции ClockW(n, x, y) и Vans(n, x, y, H, j) решают поставленную задачу.

Параметры головной функции ClockW(n, x, y) - это размер доски (n) и начальная точка (x, y), с которой начинается перемещение коня. В ClockW() инициируется нулями доска-матрица H размером n´n и осуществляется первый ход. Далее реализуется обращение к рекурсивной функции Vans() и после вычислений выводится матрица H с полным или неполным туром коня. В последнем случае непройденные поля остаются помеченными нулями.

Параметры рекурсивной функции Vans(n, x, y, H, j) - это размер доски (n), точка (x, y), с которой осуществляется очередной ход коня, доска (H) и глубина рекурсивных обращений (j). Функция Vans() возвращает текущее состояние матрицы. Поскольку текст функции Vans(n, x, y, H, j) достаточно адекватно отражает суть ранее описанного D-алгоритма, то мы не будем останавливаться на её дополнительном описании. Напомним лишь, что используемая в Vans() константа D - это конкретная матрица приращений для формирования очередного хода коня.

Контрольные примеры:

1. Пусть n=8 и

Просчет по программе ClockW(n, x, y) позволяет найти обходы доски 8´8 с каждого из 64 её полей. Нетрудно подобрать и другие матрицы D с этим же свойством.

2. Пусть n=2 и

Просчет по программе ClockW(n, x, y) позволяет найти обходы доски 12´12 с каждого из 144 её полей. Если сами обходы нас не интересуют, а требуется лишь подтверждение их существования, то запускать программу ClockW(n, x, y) 144 раза вряд ли целесообразно. Проще воспользоваться функцией prov(n), которая по входному параметру n (размер доски) выдает первый найденный контрпример или подтверждение “yes”, если удается построить обходы с каждого поля:

3. Для ускорения вычислений можно построить аналоги программ-функций ClockW(), Vans() и prov() на каком-либо языке программирования компилирующего типа. Например, реализация этих программ на Delphi 5 (Object Pascal) позволила найти D-алгоритмы обхода досок с любого поля для широкого диапазона значений n. Некоторые из полученных результатов сведены в таблицу 1.

Таблица 1

D-алгоритмы обхода доски размером n´n с каждого её поля

Матрица D для формирования ходов коня

и разрешения неопределенных ситуаций

Применимость

D-алгоритма (n= …)

 1.

8,10,12,14,18

 2.

6,12,14,16

 3.

6,10,12,20

 4.

6,14,18,22

 5.

8,10,14,24

Home Содержание Схемы ООД Доска объявлений Поиск