Turbo Pascal - Ход конем

Конь - шахматная фигура с самым интересным способом атаки. Ходить конь может по букве "Г" (две клетки вперед, одну в сторону). Поскольку правило перемещения коня коренным образом отличается от перемещений других фигур, то фраза "совершить ход конем" значит сделать неординарный поступок.

Обход конем - одна из самых древних шахматных задач. Смысл задачи о коне сводится к нахождению маршрута, при котором конь побывает на всех клетках шахматной доски по одному разу. Количество замкнутых и незамкнутых маршрутов зашкаливает за миллиарды и конечная цифра неизвестна до сих пор. Количество клеток на доске для задачи "Обход конем" может быть различным. Существует множество решений задачи. Приведем основные три.

Правило Варнсдорфа

Согласно правилу Варнсдорфа коня следует ставить на ту клетку, из которой фигура имеет возможность имеет сделать минимальное число ходов по клеткам, которые были еще не пройдены. Правило Варнсдорфа - одно из наиболее простых.

Метод Вандермонда

Арифметическое решение задачи о коне. Маршрут фигуры задается в виде последовательности дробей x/y, где значения x и у являются координатами на шахматной доске. Разность x2 - x1 может быть только равно единице или двойке, также как и разность y2 - y1 равные двойке или единице. В целом, можно сказать, что метод Вандермонда является разновидностью метода Эйлера для четного случая размерности доски.

Метод Эйлера

Метод Эйлера достаточно прост для понимания. Фигура двигается по случайному маршруту до тех пор, пока не закончатся все ходы. После этого оставшиеся поля добавляются в итоговый маршрут после определенной перегруппировки элементов.

Решение задачи о коне на Паскале

Обход конем в Pascal можно решить двумя основными способами

Turbo pascal Ход конем - интерактивная программа

Суть данного метода заключается в переборе возможных вариантов хода конем и последовательным исключением пройденных клеток. В качестве аналога шахматной доски инициализируется массив 8x8. После посещении фигурой позиции в последнюю записывается "1", свободные поля обозначаются "0". В том случае если во всех позициях для возможных вариантов хода записаны единицы, а на доске имеются нулевый ячейки, происходит отмена хода.

Turbo pascal Ход конем - рекурсивная программа

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

Данные методы для решения задачи "ход коня" в Pascal можно применять, используя алгоритмы оптимизации рассмотренные выше. Исходный код программы "Ход конем в pascal" можно скачать ниже.

Скачать:

Обход конем - Решение задачи о коне в графическом режиме Паскаля

Ход коня - Определение в Turbo Pascal возможных маршрутов коня по введенной матрице