Внимание! Это сайт переехал на www.simplecoding.org
Эта интересная головоломка была предложена математиком Эйлером. Задание, на первый взгляд, достаточно простое – нужно шахматным конем, находящимся на произвольной клетке шахматной доски, обойти все остальные клетки доски. При этом на одну клетку можно походить только один раз.
Конь, как известно, ходит Г-образно. Т.е. на две клетки в каком-либо направлении (вверх, вниз, вправо, влево) и на одну клетку в перпендикулярном. Таким образом, конем, можно сделать максимум восемь различных ходов из заданной клетки (или меньше, если конь находится у края доски).
Для решения этой задачи на компьютере необходимо разработать правила, в соответствии с которыми компьютер будет выбирать ход. В принципе, очередной ход можно выбирать случайным образом. Но ожидать при этом хороших результатов может только большой оптимист. Интересный вариант выбора ходов предложен в книге "Как программировать на С++" Х.Дейтел, П.Дейтел.
Для его реализации нужны два двумерных массива (размер 8х8). В первый массив (board) записываем данные о том, ходили ли мы на какую-то клетку. Например, в начале все элементы массива равны нулю. Как только мы ставим коня на какую-либо клетку соответствующему элементу массива нужно присвоить единицу. Здесь все просто. Заполнение второго массива (accessibility - доступность) немного сложнее. Каждый его элемент, также как и в массиве board, соответствует клетке на доске, но здесь мы записываем информацию о том, со скольких клеток можно походить на заданную. Например, на клетку а1 можно походить из двух клеток (с2 и b3). Массив accessibility перед началом решения задачи имеет следующий вид:
| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
Рис.1
После хода конем на какую-нибудь клетку мы должны будем уменьшить на единицу значения всех элементов массива accessibility, которые соответствуют клеткам, находящимся на расстоянии одного хода от текущей клетки. Изменять значение элемента массива accessibility для текущей клетки не имеет смысла, т.к. соответствующий элемент массива board имеет значение равное единице (на эту клетку ходить нельзя).
Имея эти два массива выбрать ход не сложно. Нужно ходить на те клетки, для которых элементы массива accessibility имеют минимальное значение, а элементы массива board равны нулю.
Можно углубить анализ, т.е. просчитывать несколько ходов вперед. В этом случае нужно выбирать тот ход, который приводит нас к ячейке с минимальным значением элемента в массиве accessibility.
Кроме этого, я хотел бы пояснить, как выполняется ход. Мы уже говорили, что существует восемь возможных ходов. Все они закодированы цифрами от 0 до 7. На рис. 2 показаны все возможные варианты ходов.
| 2 | 1 | ||||||
| 3 | 0 | ||||||
| K | |||||||
| 4 | 7 | ||||||
| 5 | 6 | ||||||
Рис.2
Каждый ход можно представить как перемещение на заданное количество клеток по горизонтали и по вертикали. Например, нулевому ходу соответствует перемещение на две клетки по горизонтали, и "-1" клетку по вертикали (знак минус указывает на направление перемещения). Для выполнения ходов удобно использовать следующие массивы:
int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2}; int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};
Значения элементов этих массивов соответствуют перемещению по горизонтали и по вертикали для всех возможных ходов. Например, для выполнения хода 4 нужно выполнить две операции:
X += horizontal[4]; Y += vertical[4];
где, X и Y – текущие координаты (по горизонтали и вертикали, соответственно).
Скачать программу (knight.zip - 250kB)
Скачать исходники (knight_src.zip - 16,4kB) (Для компиляции необходим Borland C++ Builder 5)