можно ли ходом коня обойти все клетки шахматной доски начав с клетки а1
Можно ли ходом коня обойти все клетки шахматной доски начав с клетки а1
157. О ходе шахматного коня
Мы встречались уже в этом разделе с вопросом, может ли конь обойти часть шахматной доски, побывав при этом на каждом поле только один раз.
Вот еще одна старинная задача о ходе шахматного коня:
Требуется обойти конем все 64 клетки шахматной доски так, чтобы на каждой клетке конь был только один раз и затем возвратился бы в клетку, из которой вышел.
Задачей этой занимался Эйлер и в письме к Гольдбаху (26 апреля 1757 года) дал одно из решений ее. Вот что, между прочим, пишет он в этом интересном письме:
«. Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения. Вопрос состоит в следующем. Требуется обойти шахматным конем все 64 клетки шахматной доски так, чтобы на каждой клетке он побывал только один раз. С этой целью все места, которые занимал конь при своих последовательных ходах, закрывались марками. Но к этому присоединилось еще требование, чтобы начало хода делалось с данного места. Это последнее условие казалось мне очень затрудняющим вопрос, так как я скоро нашел некоторые пути, при которых, однако, выбор начала для меня свободен. Я утверждаю, однако, что если полный обход коня будет возвратный, т. е. если конь из последнего места опять может перейти на первое, то устраняется и это затруднение. После некоторых изысканий по этому поводу я нашел, наконец, ясный способ находить сколько угодно подобных решений (число их, однако, не бесконечно), не делая проб. Подобное решение представлено на рисунке (рис. 153).
Рис. 153
Конь ходит в порядке, указанном числами. Так как из последнего места 64 он может перейти на 1, то этот полный ход есть возвратный».
Таково решение задачи о ходе шахматного коня, данное Эйлером. В письме не указаны ни приемы, ни путь, которыми знаменитый ученый пришел к своему открытию. Сейчас мы укажем на методы иных, более симметричных и методичных решений.
Разделим шахматную доску на две части: внутреннюю, состоящую из 16 клеток, и краевую (рис. 154).
Рис. 154
Каждые 12 клеток краевой доски, обозначенные у нас Одинаковыми буквами, дают один из частных зигзагообразных путей шахматного коня вокруг доски; точно так же четыре одноименные клетки внутренней части доски дают частный замкнутый путь шахматного коня в виде квадрата или в виде ромба. Рис. 155 представляет два зигзагообразных частных пути коня на краевой части доски. Эти пути обозначим буквами а и b. Там же начерчены и два пути на внутренней части доски. Эти пути назовем a’ и b’ соответственно обозначениям на рис. 154.
Рис. 155
Итак, ставят коня на какую-нибудь клетку, например, краевой части доски и описывают по ней путь из 12 клеток; вслед за тем конь перепрыгивает на клетку одного из трех (не одноименных) внутренних путей, проходит этот путь в любом направлении и перескакивает опять на краевую часть, где снова делает следующий частный зигзагообразный путь из 12 клеток, вновь перескакивает на один из внутренних, не одноименных с предыдущим, путей, описывает его, переходит опять на новый краевой путь и т. д., пока не обойдет все 64 клетки.
Способ решения задачи настолько прост и легок, что не нуждается в более подробных разъяснениях и указаниях.
Можно эту же задачу решить и другим, не менее легким, приемом. Здесь для удобства доска делится на 4 части по 16 клеток в каждой двумя серединными линиями (рис. 156) 16 клеток каждой четверти, обозначенных одинаковыми буквами, можно соединить посредством сторон двух квадратов и двух ромбов, не имеющих ни одной общей вершины (рис. 157). Соединяя, в свою очередь, одноименные квадраты и ромбы всех четвертей доски, можно получить четыре частных круговых возвратных пути из 16 клеток. Соединяя затем эти последние пути, получим полный путь коня в 64 клетки.
Рис. 156
Рис. 157
Полезно сделать еще следующие замечания. На каждой четверти доски ромбами и квадратами обозначены по четыре пути коня. Если соединим ромбы и квадраты, обозначенные одинаковыми буквами во всех четырех четвертях доски, получим по четыре частных возвратных пути из 16 клеток.
Некоторые трудности могут представиться кому-нибудь, когда для получения полного пути в 64 клетки он начинает соединять между собой эти четыре частных пути по 16 клеток. Здесь полезно иметь в виду, что цепь (или ряд ходов) можно видоизменять, не разрывая ее. Основано это на так называемом правиле Бертрана, которое состоит в следующем.
Пусть имеем незамкнутую цепь ходов, проходящих через клетки A, B, С, D, E, F, G, H, I, J, К, L и пусть оконечности этой цепи будут А и L. Если клетка, например D, отличная от предпоследней K, находится от последней L на расстоянии хода коня, то DE можно заменить через DL и цепь ходов обратится в
т. е. вторая половина цепи будет пройдена в обратном порядке.
То же самое относится и к тому случаю, когда какая-нибудь клетка, кроме второй, сообщается ходом коня с первой. Итак, цепь (или ряд ходов) можно видоизменять, не разрывая ее.
Число путей, которыми конь может обойти доску и которые можно найти указанными выше приемами, не бесконечно. Но оно настолько огромно, что трудно его представить.
Задача о ходе коня
Анимация прохождения коня через все клетки поля шахматной доски 5 x 5
Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Содержание
Формулировка задачи [ ]
Граф, соответствующий шахматной доске 8×8. Указанные степени вершин показывают количество различных ходов коня из соответствующих полей доски.
Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.
Методы решения [ ]
Метод Эйлера [ ]
Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся непройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов.
Рассмотрим в качестве примера следующий маршрут:
| 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 |
| 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 |
Метод Вандермонда [ ]
Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей 
, где 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 |
Маршрут, найденный шахматным автоматом [ ]
Шахматный автомат нашёл замкнутый маршрут коня, изображенный на диаграмме справа.
Мнемоническое стихотворение [ ]
Обойти конём все шахматные клетки по одному разу, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно следуя стихотворению: [3]
Алеет Осень Ценными Дарами,
Еще Один Животворящий День.
Хлеба Червонят Желтыми Шнурами,
Хрустальных Вод Философична Сень.
Два Вечера Цеплявшиеся Шишки
Артист Писал, Бездонна Синева.
Дорожный Шлак Целуют Червячишки,
Еще Покрыта Флоксами Трава.
Дымится Чай Эффектней Шоколада,
Фарфоры Чашек Достаются Трем,
Блондинке Девушка Дана Отрада
Форшмак Делить Холодным Острием.
Жена, Толкая Хилую Подругу,
Желает Сняться Этим Выходным,
Ценя Сама Арктическую Вьюгу,
Бросает Шар Арбуза Четверым.
Цикад Пяток, Едва Чревовещая,
Дарует Дрему Фикусам Окна.
Хотя Довольны Жаждавшие Чая,
Хозяин Шумно Жертвует Вина.
Фокстротами Шесть Девушек Пленились,
Эстрадных Танцев Фантастичней Па,
Едва Ступающий Цыпленок Вылез,
А Селезень Блуждающий Пропал.
Алеет Тело Бронзовой Осины,
Царит Теней Ажурная Длина.
Беззвучней, Чем Автомобиля Шины,
Болоту Ветер Дарит Семена.
Фонарь Восьмью Химерами Сияет,
Жук Прилетает, Хлопая, Туда.
Желанна Осень, Если Довершает
Ценнейший Отдых Бодрого Труда.
Первые буквы задают координаты ходов:
Алеет Осень = А1; Ценными Дарами = С2; и т. д.
В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т.д.
Обобщение на произвольные доски [ ]
Замкнутые маршруты [ ]
Количество замкнутых маршрутов с учётом направления в два раза больше. Замкнутые маршруты существуют на досках для всех чётных ( Шаблон:OEIS ).
Незамкнутые маршруты [ ]
Шахматные задачки. Как ходят шахматные фигуры
Продолжаю решать шахматные задачки на Python. В прошлой задаче нужно было проверять окрашены ли заданные клетки на шахматной доске в один цвет. Теперь будут задачи на ход шахматных фигур и самая простая из них это:
Ход ладьи
Задача очень простая, чтобы решить достаточно представить себе ладью на шахматном поле и проанализировать ее ход. Ладья ходит только либо по вертикале вверх или вниз, либо по горизонтали влево или вправо. Становится ясно, что одна из координат клетки всегда остается неизменной, т.е. если ладья ходит по вертикале неизменна координата Х если по горизонтали то Y. Отсюда напишем условие при котором будем сравнивать если координаты X первой и второй клетки одинаковы или координаты Y первой и второй клетки одинаковы значит выводим YES – ладья может попасть с первой клетки на вторую, иначе – NO, не может.
Ход короля
Что не так с кодом? Все это можно было записать гораздо лаконичнее.
либо использовать функцию абсолютной величины (модуля) числа – abs()
Ход слона
Шахматный слон ходит по диагонали. Даны две различные клетки шахматной доски, определите, может ли слон попасть с первой клетки на вторую одним ходом.
Проанализируем ход. Двигая слона по шахматной клетки можно заметить, что слон всегда ходит по диагоналям квадрата, т.е. если по координате X он передвинется на 5 клеток то и по координате Y он передвинется на 5 клеток. Отсюда можем сделать вывод, что модуль разности координатов X1 и X2 и Y1 и Y2 всегда будет равен
Ход ферзя
Шахматный ферзь ходит по диагонали, горизонтали или вертикали. Даны две различные клетки шахматной доски, определите, может ли ферзь попасть с первой клетки на вторую одним ходом.
Проанализируем ход ферзя. Эта фигура ходит как король, но уже на любое доступное количество клеток, ну или можем сказать, что ферзь ходит и как ладья и как слон, мы уже анализировали и писали код для этих фигур поэтому просто объединим два условия в одно:
Ход коня
Шахматный конь ходит буквой “Г” — на две клетки по вертикали в любом направлении и на одну клетку по горизонтали, или наоборот. Даны две различные клетки шахматной доски, определите, может ли конь попасть с первой клетки на вторую одним ходом.
Самая интересная фигура. Проанализировав ход коня буквой «Г» можно увидеть что если конь ходит вниз или вверх буквой то его координата по X меняется на 1 а координата по Y на 2, если влево и вправо то наоборот X на 2 а Y на 1. Исходя из этого можно написать код, что если разность координат X1 и X2 уменьшилась или увеличилась на 1 и при этом разность координат Y1 и Y2 уменьшалась или увеличилась на 2 или если разность координат X1 и X2 уменьшилась или увеличилась на 2 и при этом разность координат Y1 и Y2 уменьшалась или увеличилась на 1 то выводим YES иначе NO
Очень страшное решение на самом деле, но рабочее. Можно и нужно было применить модуль разницы координат и ввести дополнительные переменные.
Вот такие интересные были на мой взгляд задачи. Для меня они казались сложными по началу, но если хорошенько разобраться в условии и понять как должны происходить процессы в задаче то решение приходит само по себе. Главное быть внимательным и не спешить.
Опубликованно May 13th, 2018 by Aziz Madazimov
Занимательные задачи
Задачи по теме «Раскраска»
1. Из шахматной доски 8х8 вырезали две противоположные угловые клетки. Можно ли теперь разрезать доску на доминошки (прямоугольники 2х1)?
2. В левой нижней клетке шахматной доски стоит шахматный конь. Может ли он сделать ровно 3 хода и вернуться в ту же клетку?
3. В левой нижней клетке шахматной доски стоит шахматный конь. За несколько ходов он добрался до противоположной (правой верхней) клетки. Докажите, что он сделал чётное количество шагов.
4. В каждой клетке доски 5х5 сидит жук. Хлопнули в ладоши – и каждый жук переполз в соседнюю (по стороне) клетки. Докажите, что теперь хотя бы в одной из клеток нет ни одного жука.
5. Можно ли разрезать клетчатую доску 10х10 на прямоугольники размером 4х1?
6. Замок имеет вид прямоугольника размером 7х9. Каждая клетка, кроме центральной – комната замка, а в центральной клетке находится бассейн. В каждой стене (стороне клетки), разделяющей две соседние комнаты, проделана дверь. Можно ли, не выходя из замка и не заходя в бассейн, обойти все комнаты, побывав в каждой ровно по одному разу?
7. Можно ли ходом коня обойти все клетки шахматной доски, начав с клетки a1, закончив в клетке h8 и на каждой клетке доски побывав ровно один раз?
8. Шахматную доску разбили на доминошки. Может ли среди этих доминошек оказаться 17 горизонтальных и 15 вертикальных.
1. Из шахматной доски 8х8 вырезали две противоположные угловые клетки. Можно ли теперь разрезать доску на доминошки (прямоугольники 2х1)?
Если доска разрезана на домииощки (одно поле у доминошки – белое, второе – чёрное), то под ними чёрных и белых клеток поровну. Посчитаем клетки: чёрных – 30, белых – 32.
2. В левой нижней клетке шахматной доски стоит шахматный конь. Может ли он сделать ровно 3 хода и вернуться в ту же клетку?
При ходе коня идёт чередование цвета клеток. Конь стоит на белой клетке. При первом шаге он будет стоять на чёрной клетке, при втором ходе – на белой и т.д. Если ходы нечётные, тот конь находится на чёрной клетке, если ходы чётные, то конь находится на белой клетке. На третьем ходе конь будет стоять на чёрной клетке и на первоначальную клетку не вернётся.
3. В левой нижней клетке шахматной доски стоит шахматный конь. За несколько ходов он добрался до противоположной (правой верхней) клетки. Докажите, что он сделал чётное количество шагов.
При ходе коня идёт чередование цвета клеток. Если ходы нечётные, тот конь находится на чёрной клетке, если ходы чётные, то конь находится на белой клетке. Конь будет находится на белой клетке, т.е. он сделает чётное количество шагов
4. В каждой клетке доски 5х5 сидит жук. Хлопнули в ладоши – и каждый жук переполз в соседнюю (по стороне) клетки. Докажите, что теперь хотя бы в одной из клеток нет ни одного жука.
Раскрасим доску в шахматном порядке (первая клетка – чёрная). Если жук сидел на белой клетке, то он переползёт на чёрную, и наоборот. Получим: 13 чёрных клеток, 12 – белых. 12 «белых» жуков переползут на 13 чёрных клеток, Вывод: хотя бы одна клетка будет свободна.
5. Можно ли разрезать клетчатую доску 10х10 на прямоугольники размером 4х1?
Сделаем шахматную раскраску в 4 цвета, например, коричневый, синий, зелёный и жёлтый. Для удобства можно каждый цвет назвать цифрой: 1, 2, 3, 4, тогда получим:
Глава 5. Задача о ходе коня / Математика на шахматной доске
Гик Е. Я.
Глава 5. Задача о ходе коня
Эта глава посвящена самой интересной задаче о коне и, пожалуй, вообще самой известной шахматно-математической задаче. Она заключается в нахождении маршрута коня на шахматной доске.
Обойти конем все поля шахматной доски, посетив каждое из них по одному разу.
В литературе эту задачу обычно называют просто задачей о ходе коня. Особая популярность задачи объясняется тем, что в XVIII и XIX вв. ею занимались многие крупные математики, в том числе великий Леонард Эйлер, посвятивший ей большой мемуар «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию»21. Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность, поэтому задачу часто связывают с его именем.
Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня, а в нахождении всех маршрутов и подсчете их числа. Увы, эта задача не решена до сих пор, и шансов на успех немного. Известно, правда, что число решений не превосходит C 63 168 (это число состоит из ста цифр), но больше 30 миллионов. Математик Ф. Миндинг, подошедший к проблеме с алгебраической точки зрения, предложил метод, позволяющий вывести формулу для числа всех решений, однако вычисления, которые следует при этом произвести, практически неосуществимы, и поэтому метод Миндинга представляет лишь теоретический интерес.
Литература, посвященная задаче о ходе коня, весьма обширна. Те или иные методы нахождения маршрутов можно найти в самых разнообразных источниках. Среди них следует выделить книгу Крайчика «Проблема коня», которая, как видно из названия, целиком посвящена этой теме (эта книга входит в упомянутую во введении фундаментальную работу Крайчика). Об алгебраическом подходе, основанном на исследованиях Янишад рассказывается у Окунева, а у Шуберта22 можно найти подробный исторический обзор задачи о ходе коня. Остановимся на некоторых наиболее интересных методах нахождения маршрутов коня.
