Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11639
Последний выпуск: 19.06.2015

Путешествие коня

Автор: Стаценко Владимир.
17 сентября 2006 года

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

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

Для решения этой задачи на компьютере необходимо разработать правила, в соответствии с которыми компьютер будет выбирать ход. В принципе, очередной ход можно выбирать случайным образом. Но ожидать при этом хороших результатов может только большой оптимист. Интересный вариант выбора ходов предложен в книге "Как программировать на С++" Х.Дейтел, П.Дейтел.

Для его реализации нужны два двумерных массива (размер 8х8). В первый массив (board) записываем данные о том, ходили ли мы на какую-то клетку. Например, в начале все элементы массива равны нулю. Как только мы ставим коня на какую-либо клетку соответствующему элементу массива нужно присвоить единицу. Здесь все просто. Заполнение второго массива (accessibility - доступность) немного сложнее. Каждый его элемент, также как и в массиве board, соответствует клетке на доске, но здесь мы записываем информацию о том, со скольких клеток можно походить на заданную. Например, на клетку а1 можно походить из двух клеток (с2 и b3). Массив accessibility перед началом решения задачи имеет следующий вид:

23444432
34666643
46888864
46888864
46888864
46888864
34666643
23444432
Рис.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 - текущие координаты (по горизонтали и вертикали, соответственно).

Вы можете скачать исходный код [6.3Kb], описанного алгоритма, или готовую программу [223Kb].

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
32K
28 октября 2007 года
semenov-aks
7 / / 28.10.2007
Мне нравитсяМне не нравится
29 октября 2007, 08:32:11
Потрясен :)
Уже несколько лет забавляюсь подобной вещью, только на бумаге. Заполнял таким образом самые различные матрицы: 8х8, 5х5, 6х7 и т.д.
Написать прогу как-то в голову не пришло :))
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог