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


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

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

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

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

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

Для его реализации нужны два двумерных массива (размер 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
К
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 - текущие координаты (по горизонтали и вертикали, соответственно).

Шахматные программы

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Путешествие коня" в других словарях:

  • Альфонс садится на коня — Жанр: стихотворение Автор: Александр Сергеевич Пушкин Язык оригинала: русский Год написания: 1835 год или 1836 год …   Википедия

  • Русская литература — I.ВВЕДЕНИЕ II.РУССКАЯ УСТНАЯ ПОЭЗИЯ А.Периодизация истории устной поэзии Б.Развитие старинной устной поэзии 1.Древнейшие истоки устной поэзии. Устнопоэтическое творчество древней Руси с X до середины XVIв. 2.Устная поэзия с середины XVI до конца… …   Литературная энциклопедия

  • Александр II (часть 1, I-VI) — — Император Всероссийский, старший сын Великого Князя — впоследствии Императора — Николая Павловича и Великой Княгини Александры Феодоровны; родился в Москве 17 го апреля 1818 г.; объявлен Наследником престола 12 го декабря 1825 …   Большая биографическая энциклопедия

  • Повести о Дунке и Эгге — Tales of Dunk and Egg Автор: Мартин, Джордж Реймонд Ричард Жанры: Фэнтези Страна …   Википедия

  • Маркхэм, Клемент — Клемент Роберт Маркхэм Clements Robert Markham К …   Википедия

  • Петушкова, Елена Владимировна — Елена Петушкова …   Википедия

  • ГЕОРГИЙ — [греч. Γεώργιος] († 303), вмч. (пам. 23 апр., 3 нояб., пам. рус. 26 нояб., пам. груз. 10 нояб.). Один из наиболее известных святых в христ. мире, а в нек рых странах (напр., в Грузии и Англии) самый почитаемый. Претерпевший особо тяжелые… …   Православная энциклопедия

  • Никитин Афанасий — (?  1474/1475), путешественник, тверской купец. Совершил путешествие в Персию, Индию (1468 74). На обратном пути посетил африканский берег (Сомали), Маскат, Турцию. Путевые записки Никитина «Хождение за три моря»  ценный литературно исторический… …   Энциклопедический словарь

  • Назад в будущее 3 — Эта статья посвящена последней части трилогии Назад в будущее Назад в будущее 3 Back to the Future Part III …   Википедия

  • Слейпнир — («скользящий» или «живой, проворный, шустрый»[1])  в германо скандинавской мифологии восьминогий конь Одина, порождение Локи …   Википедия

Книги

Другие книги по запросу «Путешествие коня» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.