Заполнить шахматную доску ходом коня
Обновлено: 20.05.2024
Дана шахматная доска. На ней есть только одна фигура — конь. Как известно, конь в шахматах ходит буквой «Г». Задача — посетить все клетки шахматного поля, при этом остановиться в каждой клетке конь может только один раз. Например, конь стартует из позиции B1:
Обход нерекурсивный. Старый добрый брутфорс во всей красе ? Зато память не жрёт и работает шустро!
Для решения важно понимать, что теоретически из любой клетки у коня всего 8 возможных ходов:
| 6 | 8 |
| 5 | 7 |
| X | |
| 1 | 3 |
| 2 | 4 |
Реализуем эти ходы с помощью двух одномерных массивов (массивы объявлены как константы, это защитит их от случайного изменения). Один отвечает за смещение по строкам (по вертикали), а другой по столбцам (по горизонтали). Примем точку, в которой стоит конь (в таблице — X) за 0, тогда ходы из таблицы можно записать так:
Саму шахматную доску реализуем с помощью одного двумерного массива. Нужно отметить, что в программировании при указании индексов двумерного массива первый индекс указывает на номер строки (вертикаль), а второй — на индекс столбца (горизонталь). Если провести аналогию с математикой (системой Декартовых координат), то в математике наоборот, первая координата — это X, т.е точка по горизонтали, а вторая координата — это Y — точка по вертикали. Это так… напоминание для пытливых умов во избежание путаницы. Итак, решение:
На процессоре i3 решение из начальных позиций, где по правилам игры изначально стоит конь заняло:
- Из позиции B1 ~ 2.5 — 3 сек
- Из позиции B8 ~ 10 мин
- Из позиции G1 ~ 2 мин
- Из позиции G8 ~ 1 сек
Из позиции D5 решение было найдено меньше, чем за секунду, а из A1 — за 5 минут.
Если кому-то интересно, то можно модифицировать задачу, например, дав пользователю возможность вводить размер доски. Но. При увеличении поля время поиска решения будет значительно увеличиваться.
В данном решении время обхода очень сильно зависит от заданной последовательности ходов:
То есть, можно так подобрать последовательность, что решение будет найдено при первом же проходе из начальной точки, т.е. в данном случае на шаге (-1, -2). А может быть найдено и на последнем (2, 1), т.е. из начальной точки будут сначала проверены 7 ходов, а это займёт очень много времени, и только ход № 8 со стартом из начальной точки (2, 1) приведёт к решению задачи.
P.S.: Решение обкатал на нескольких стартах, вроде бы всё работает. Если найдёте ошибки — пишите, всё поправлю. И ещё: результата, когда обход доски невозможен, я не дождался. Уж очень долго придётся ждать полного обхода + нужно знать, из какой клетки обход невозможен, т.к. методом научного тыка можно целый год искать эту клетку (ну или эти клетки).
УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»
Статья опубликована в журнале "Мир ПК", 2003. №1. C.152-155.
Задача о ходе коня
Анатолий Шалыто, Никита Туккель, Никита Шамгунов
В статье рассматривается классическая задача о ходе коня, для решения которой разработаны итеративная, рекурсивная и автоматная программы. Приводятся результаты исследования этих программ. Построенная автоматная программа позволяет получить те же результаты, что и итеративная, но является более понятной.
Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию.
К одному из наиболее интересных разделов программирования относятся задачи из области искусственного интеллекта, в которых решение ищется методом "проб и ошибок" [1,2]. При этом имеет место перебор при поиске решения, продолжительность которого может быть сокращена за счет применения тех или иных эвристических правил - методов оптимизации.
Класс алгоритмов, позволяющий решать подобные задачи, в англоязычной литературе называется "backtracking algorithms" ("алгоритмы с возвратом"). Такие алгоритмы применяются в тех случаях, когда не подходят более "направленные" методы [3].
Исследуем одну из наиболее известных задач этого класса - задачу о ходе коня 4. Она состоит в том, чтобы найти обход доски размером NxM конем, перемещающимся по правилам шахматной игры. Если такой обход существует, то каждое поле посещается только один раз (выполняется NxM-1 шагов). Проанализируем методы оптимизации и исследуем работу итеративной, рекурсивной и автоматной программ.
Методы оптимизации
- определение клеток, обход из которых невозможен (оптимизация 1);
- выявление заблокированных клеток (оптимизация 2);
- применение правила Варнсдорфа (оптимизация 3);
- использование различных массивов ходов коня (оптимизация 4).
1. Определение клеток, обход из которых невозможен
Если количество клеток доски нечетно (число белых и черных клеток отличается на единицу), то обход из некоторых клеток не существует. Отметим, что путь коня проходит по клеткам, чередующимся по цвету. Если общее число клеток доски нечетно, то первая и последняя клетки пути, пройденного конем, будут одного и того же цвета. Таким образом, обход будет существовать только тогда, когда он начнется клеткой того цвета, который имеют наибольшее число клеток.
Выполнение этого условия проверяется следующей функцией:
Однако приведенное правило не охватывает всех клеток, для которых обхода не существует. Так, для доски размером 3x7, помимо тех клеток, для которых выполняется приведенное правило, обход невозможен также из клетки (2,4).
2. Выявление заблокированных клеток
Если при очередном ходе образуется клетка, куда можно войти, но откуда нельзя выйти, то такой ход недопустим, за исключением предпоследнего в обходе. Данный метод оптимизации позволяет значительно сократить число возвратов, в том числе и при совместном использовании с правилом Варнсдорфа.
Развитием этого метода является определение групп заблокированных клеток, связанных друг с другом, но отрезанных от остальной части доски. В рассматриваемой программе определяются группы из двух заблокированных клеток, что значительно уменьшает количество возвратов для небольших досок, а при использовании вместе с правилом Варнсдорфа - и для больших (например, размером 100*100 клеток).
3. Применение правила Варнсдорфа
Среди многих эвристических методов [5], используемых для сокращения перебора, правило Варнсдорфа является наиболее простым. В соответствии с ним при обходе доски коня следует каждый раз ставить на то поле, из которого он может сделать наименьшее число ходов по еще не пройденным полям. Если таких полей несколько, то можно выбрать любое из них, что может, однако, завести коня в тупик и потребовать возврата [5]. Отметим, что наилучшим образом правило Варнсдорфа работает для угловых полей.
4. Использование различных массивов ходов коня
Ходы коня могут быть заданы, например, в виде следующего массива:
Каждый его элемент определяет один возможный ход коня и содержит изменения его координат на доске при совершении хода. При использовании различных массивов для ходов коня количество возвратов может различаться. В программе применяются пять эвристически выбранных массивов, содержащих возможные ходы коня в различном порядке. Также задается максимальное число возвратов (GOOD_RET), и когда оно будет достигнуто, поиск пути начинается заново с использованием уже другого массива. При поиске обхода с применением последнего массива количество возвратов ограничивается значением MAX_RET. Если при совместном использовании всех предложенных методов оптимизации установить значение GOOD_RET равным единице, то для досок, близких к квадратным, можно строить обходы без единого возврата для всех клеток, из которых существует обход. Обход без единого возврата из каждой клетки не удается получить для "вытянутых" досок (например, 14*3) и для больших досок, например для доски 100*100 клеток.
Итеративная программа
Полный перебор
- на каждом шаге ищется фрагмент пути, начинающийся из текущей клетки и не включающий уже пройденные;
- при совершении хода из массива возможных ходов извлекается очередной элемент, который приводит в незанятую клетку, находящуюся в пределах доски;
- если ход невозможен, то происходит возврат в предыдущую клетку (отмена хода);
- поиск пути считается успешным тогда, когда номер текущего хода станет равным количеству клеток на доске. Если из начальной клетки перебраны все возможные ходы, то пути не существует.
Ниже приведена структура функции, выполняющей перебор:
Номер использованного варианта хода для каждого из ходов запоминается в массиве, размер которого выбирается в соответствии с размером доски.
Описанный алгоритм осуществляет перебор вариантов и находит решение, если оно имеется. Отсутствие решения приводит к полному перебору всех вариантов.
Для иллюстрации выполнения возвратов в табл. 1 приведен протокол обхода доски размером 3 4 из клетки с координатами (2,4). В конце протокола приведен полученный в результате обхода путь.
Таблица 1. Протокол обхода доски размером 3 4 из клетки (2,4)
Для некоторых клеток программа работает чрезвычайно медленно уже при небольших размерах доски. Например, для доски 6 6 при старте из клетки (5,2) поиск пути требует более 290 миллионов возвратов.
Результаты работы программы с оптимизацией
- не существует ни одного обхода при N, M = 7; N >= 4, M >= 5.
Переходя к изложению полученных результатов отметим, что они относятся к перечисленным выше методам оптимизации и эвристически выбранным массивам вариантов для хода коня. При применении других методов оптимизации [5] и иных массивов получаемые результаты могут различаться.
Рассмотрим результаты обхода некоторых досок. Для них приводятся таблицы, в которых указывается количество возвратов, выполненное при нахождении обхода из соответствующей клетки. При отсутствии обхода в клетке указывается символ "N". В случае, если количество возвратов превысило задаваемую в программе величину (MAX_RET = 400000), поиск пути прекращается, а в соответствующей клетке выводится сокращение "LIM". В таблицах, построенных для метода оптимизации, использующего различные массивы вариантов хода коня, в клетке дополнительно указывается обозначение массива (от 'A' до 'E'), при применении которого обход был получен без возвратов (GOOD_RET = 1). При этом, если результат был получен для первого массива, то соответствующий ему символ 'A' не выводится.
Также в таблицах приводится один из полученных путей.
Результаты, полученные для доски размером 5 5, приведены в табл. 2.
В этой программе могут быть использованы все виды оптимизаций, описанные выше.
Автоматная программа
Если первые две программы для решения этой задачи вполне традиционны [2], то автоматные к таковым не относятся.
Отметим, что автоматная программа может быть формально построена по описанной выше итеративной программе с помощью метода, изложенного в работе [7]. Автоматная программа может быть также формально построена и по приведенной рекурсивной программе с использованием метода, предложенного в работе [8].
Кроме того, можно создать автоматную программу путем непосредственного построения автомата по условиям задачи. На рис. 1, 2 для этого автомата приведены соответствующие схема связей и граф переходов автомата Мили.
Рис. 1. Схема связей автомата для задачи о ходе коня
Этот автомат использует функции и переменные, определенные в итеративной программе. Поэтому в автоматной программе применяются все рассмотренные методы оптимизации, а получаемые с ее помощью результаты совпадают с результатами работы итеративной программы.
Рис. 2. Граф переходов автомата для задачи о ходе коня
Упрощенный текст функции, реализующей этот автомат, приведен ниже:
Заключение
Совместное применение достаточно простых и известных методов оптимизации позволило резко сократить перебор, благодаря чему удается относительно быстро находить пути в досках весьма большой размерности. Так, на компьютере, оснащенном процессором Pentium II 400 МГц, поиск обхода из каждой клетки доски размером 200 200 занял около 20 минут (на поиск одного обхода - около 0,03 с). При этом для большинства клеток обход выполняется без единого возврата назад. В программе, наряду с рассмотренными, могли бы использоваться и другие методы оптимизации [5]. Однако на досках очень большого размера, например 2000x2000 клеток, нахождение даже одного пути занимает значительное время и при применении методов оптимизации, позволяющих строить обходы без единого возврата.
Как было отмечено выше, итеративная, рекурсивная и автоматная программы позволяют получать одинаковые результаты, однако автоматная более понятна за счет явного выделения состояний.
Настоящая работа была выполнена на кафедре "Компьютерные технологии" Санкт-Петербургского государственного института точной механики и оптики (технического университета). Авторы благодарны студенту этой кафедры Григорьеву А.Э., который принимал участие в начале этой работы.
Работа выполнена при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 "Разработка технологии автоматного программирования".
Литература
- Бобак И. Алгоритмы: AI поиск //Программист. 2002. №7.
- Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир: Мир, 1985.
- Бобак И. Алгоритмы: "возврат назад" и "разделяй и властвуй" //Программист. 2002. №3.
- Гарднер М. Математические новеллы. М.: Мир, 1974.
- Гик Е. Шахматы и математика. М.: Наука, 1983.
- Шалыто А.А., Туккель Н.И. Реализация автоматов при программировании событийных систем //Программист. 2002. №4.
- Шалыто А.А. Туккель Н.И. Реализация вычислительных алгоритмов на основе автоматного подхода //Телекоммуникации и информатизация образования. 2001. №6.
- Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы // Программист. 2002. №8.
ОБ АВТОРАХ
Шалыто Анатолий Абрамович - ученый секретарь Федерального научно-производственного центра (ФНПЦ) - Федерального государственного унитарного предприятия (ФГУП) "НПО "Аврора"", профессор кафедры "Компьютерные технологии" СПбГИТМО (ТУ). С ним можно связаться по адресу: mail@avrorasystems.com ("для Шалыто").
Шамгунов Никита Назимович - трехкратный чемпион Урала по программированию, двухкратный финалист чемпионатов мира по программированию ACM, аспирант СПбГИТМО (ТУ).
Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года). В письме к Гольдбаху он сообщал:
| …Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб. |
| 55 | 58 | 29 | 40 | 27 | 44 | 19 | 22 |
| 60 | 39 | 56 | 43 | 30 | 21 | 26 | 45 |
| 57 | 54 | 59 | 28 | 41 | 18 | 23 | 20 |
| 38 | 51 | 42 | 31 | 8 | 25 | 46 | 17 |
| 53 | 32 | 37 | a | 47 | 16 | 9 | 24 |
| 50 | 3 | 52 | 33 | 36 | 7 | 12 | 15 |
| 1 | 34 | 5 | 48 | b | 14 | c | 10 |
| 4 | 49 | 2 | 35 | 6 | 11 | d | 13 |
Сначала попытаемся из незамкнутого маршрута сделать замкнутый. Для этого рассмотрим, куда можно пойти с полей 1 и 60. С поля 1 можно пойти на поля 2, 32 и 52, а с 60 - на 29, 51 и 59. В этих двух наборах есть поля, различающиеся на единицу, а именно - 51 и 52. Благодаря этому можно сделать маршрут замкнутым, обратив его часть. Для этого перенумеруем поля с 52 по 60 в обратном порядке. После этого у нас получается замкнутый маршрут:
| 57 | 54 | 29 | 40 | 27 | 44 | 19 | 22 |
| 52 | 39 | 56 | 43 | 30 | 21 | 26 | 45 |
| 55 | 58 | 53 | 28 | 41 | 18 | 23 | 20 |
| 38 | 51 | 42 | 31 | 8 | 25 | 46 | 17 |
| 59 | 32 | 37 | a | 47 | 16 | 9 | 24 |
| 50 | 3 | 60 | 33 | 36 | 7 | 12 | 15 |
| 1 | 34 | 5 | 48 | b | 14 | c | 10 |
| 4 | 49 | 2 | 35 | 6 | 11 | d | 13 |
Теперь можно включить в маршрут некоторые из непройденных клеток. Так как наш маршрут замкнутый, то его можно разорвать в произвольном месте и к одному из концов прицепить подходящую цепочку из непройденных клеток. Например, если разорвать цепочку в клетке 51 (перенумеровав клетки и сделав её последней, а 52 - первой), то сможем удлинить нашу цепочку на клетки a, b и d, которые станут клетками 61, 62 и 63.
Метод Вандермонда
, где x и y — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8.
Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности.
Правило Варнсдорфа
Правило Варнсдорфа, являющееся разновидностью жадного алгоритма для отыскания маршрута коня, формулируется так:
При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них.
Долгое время считалось, что правило Варнсдорфа работает безукоризненно. Позднее с помощью компьютеров была установлена неточность во второй его части: если существует несколько подходящих полей, то не все они равноценны, и произвольный выбор поля может завести коня в тупик. На практике однако вероятность попадания в тупик невелика даже при вольном пользовании второй частью правила Варнсдорфа. [2]
Примечательные маршруты
Маршрут Яниша
| 50 | 11 | 24 | 63 | 14 | 37 | 26 | 35 |
| 23 | 62 | 51 | 12 | 25 | 34 | 15 | 38 |
| 10 | 49 | 64 | 21 | 40 | 13 | 36 | 27 |
| 61 | 22 | 9 | 52 | 33 | 28 | 39 | 16 |
| 48 | 7 | 60 | 1 | 20 | 41 | 54 | 29 |
| 59 | 4 | 45 | 8 | 53 | 32 | 17 | 42 |
| 6 | 47 | 2 | 57 | 44 | 19 | 30 | 55 |
| 3 | 58 | 5 | 46 | 31 | 56 | 43 | 18 |
Примечателен маршрут коня, найденный К. Я. Янишем: он образует полумагический квадрат, а при повороте доски на 180° первая половина маршрута (номера с 1 до 32) переходит во вторую (номера с 33 по 64).
Маршрут, найденный шахматным автоматом
Шахматный автомат нашёл замкнутый маршрут коня, изображенный на диаграмме справа.
Мнемоническое стихотворение
Обойти конём все шахматные клетки и ни разу не побывать дважды на одной и той же, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно благодаря стихотворению: [3]
Алеет Осень Ценными Дарами,
Еще Один Животворящий День.
Хлеба Червонят Желтыми Шнурами,
Хрустальных Вод Философична Сень.
Два Вечера Цеплявшиеся Шишки
Артист Писал, Бездонна Синева.
Дорожный Шлак Целуют Червячишки,
Еще Покрыта Флоксами Трава.
Дымится Чай Эффектней Шоколада,
Фарфоры Чашек Достаются Трем,
Блондинке Девушка Дана Отрада
Форшмак Делить Холодным Острием.
Жена, Толкая Хилую Подругу,
Желает Сняться Этим Выходным,
Ценя Сама Арктическую Вьюгу,
Бросает Шар Арбуза Четверым.
Цикад Пяток, Едва Чревовещая,
Дарует Дрему Фикусам Окна.
Хотя Довольны Жаждавшие Чая,
Хозяин Шумно Жертвует Вина.
Фокстротами Шесть Девушек Пленились,
Эстрадных Танцев Фантастичней Па,
Едва Ступающий Цыпленок Вылез,
А Селезень Блуждающий Пропал.
Алеет Тело Бронзовой Осины,
Царит Теней Ажурная Длина.
Беззвучней, Чем Автомобиля Шины,
Болоту Ветер Дарит Семена.
Фонарь Восьмью Химерами Сияет,
Жук Прилетает, Хлопая, Туда.
Желанна Осень, Если Довершает
Ценнейший Отдых Бодрого Труда.
Первые буквы задают координаты ходов:
Алеет Осень = А1; Ценными Дарами = С2; и т. д.
В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т.д.
Обобщение на произвольные доски
Для неквадратных досок обход конём существует только при выполнении следующих условий: если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7; если же обе стороны больше 3, то обход коня возможен на всех досках, кроме 4×4. В частности, для квадратных досок решение существует при размерах 5×5 и более.
Не так давно мне попалась интересная задачка, условием и решением которой я хочу поделиться. Надеюсь, это не будет жутким “баяном”. Итак, представим себе стандартную шахматную доску 8x8, на которой нет ни одной фигуры. Далее, мы случайным образом помещаем коня в любую клетку. Задача — определить вероятность, что после N ходов случайным образом он останется на шахматной доске. Предполагается, что если конь покидает доску, то не может войти заново. А каждый из возможных ходов является равновероятным. Другими словами, необходимо реализовать функцию:
где N — количество ходов, а x и y — координаты начальной позиции.
Если несколько вариантов решения данной задачи: цепи Маркова и динамическое программирование. Здесь я хочу предложить решение, используя прием динамического программирования. Идея заключается в том, чтобы при каждом i-ом ходе отслеживать вероятность того, что конь окажется в определенной клетке.
Из каждой позиции конь может сделать один из 8 возможных ходов (серым обозначены возможные ходы)
Все возможные позиции для текущей клетки удобно записать, если ввести 2 массива:
тогда следующее состояние будет
Далее введем массив probability[steps][xPos,yPos], где steps — количество уже сделанных шагов, а xPos и yPos — координаты клеток доски. В стартовой клетке вероятность равна 1, а на всех остальных равна 0. После каждого хода вероятность на одной из возможных клеток будет составлять 1/8, а на остальных останется 0. Тогда после N ходов для любой определенной клетки вероятность будет находиться как сумма вероятностей возможных клеток за N-1 ходов. Таким образом, мы можем подсчитать вероятность после каждого хода для всех 64 клеток и получим алгоритм:
Жду комментариев и, возможно, других способов решения данной задачки. Готовую реализацию можно скачать здесь.
Популярная головоломка о том, как обойти конем все клетки шахматной доски, побывав на каждой из них только один раз, известна уже много сотен лет. Ещё в 1749 году знаменитый математик Эйлер обратил на неё внимание, результатом чего стало: «Решение одного любопытного вопроса, который, кажется, не поддается никакому исследованию».
Многие известные математики обращали свое внимание на эту задачу, так как им была интересна ее математическая составляющая. Проблема заключается не в самом решении этой задачи или пути коня по доске, а в нахождении всех возможных вариантов и их подсчете. Можете представить себе, количество путей коня не менее 30 миллионов!
Что касается решения непосредственно задачи, то есть много различных подходов. Рассмотрим пару, на мой взгляд самые простые:
- Правило Варнсдорфа гласит, что на каждом ходу коня следует выбирать то поле, с которого он может сделать наименьшее число ходов на непройденные клетки шахматной доски. Например, проходя конем свой путь вы попадаете близко к углу шахматной доски, если есть возможность пойти в самый угол, то вы так и должны сделать, ибо выход из угла имеет только 1 путь, через 1 поле (через 1 попадаем в угол, через второе выходим), а 1 – наименьшее число ходов на непройденные ещё поля.
- Метод Полиньяка и Роже заключается в делении шахматной доски на 4 равных квадрата, в каждом из которых прописываем буквы a,b,c,d, как показано на рисунке. Конь может начать свой путь с любой буквы, проходит выбранную букву в 1 квадрате, переходит к той же букве в следующем квадрате и так далее. По прохождении полностью первой буквы, например «a» переходим к следующей букве, допустим «b» и так 4 круга проходите конём все поля шахматной доски.
Задачу о шахматном коне я даю начинающим шахматистам уже на первых уроках. Но не для того, чтобы они решили её разными методами или заполнили полностью шахматную доску на листочке в квадрат всеми цифрами от 1 до 64. А чтобы развивать понимание начинающего, как ходит конь, сколько вариантов ходов у шахматного коня из того или иного положения, чтобы сложилось в уме видение дальнейших возможных ходов этой удивительной шахматной фигуры.
Эта задача полезна не только тем, кто только учится играть в шахматы, но и «продвинутым» начинающим, крайне рекомендую практиковаться в ней.
Читайте также: