Как конем обойти всю доску


Несколько иное воплощение абстрактной схемы перебора с возвратом можно применить к другой известной задаче об обходе конем шахматной доски размера n ? n . Будем считать, что строки и столбцы доски пронумерованы соответственно сверху вниз и слева направо цифрами от 0 до n— 1, а конь перемещается по доске согласно обычным шахматным правилам. Найти обход доски с конкретного поля — значит получить последовательность позиций перемещения коня такую, что каждое поле посещается им ровно один раз. Для доски 8 ? 8 эта задача впервые была поставлена Л.Эйлером.

адача 4. Обход доски конем. На шахматной доске размера n ? n в позиции ( x, y ) находится конь (см. рис.2). Составить рекурсивную программу-функцию, находящую методом перебора с возвратом обход доски конем, если он существует. При отсутствии обхода должно быть выдано соответствующее сообщение.

Решение. На рис.2 приведен фрагмент доски. Конь K стоит в позиции ( x, y ). Клетки с цифрами вокруг K — это поля, на которые конь может переместиться из ( x, y) (0 ? x, y ? n— 1) за один ход. Множество этих полей обозначим через M(x, y ). Для фиксированного поля ( x, y ) множество M(x, y ) может содержать от двух до восьми элементов. Попробуем упорядочить эти множества. Рассмотрим вспомогательную матрицу приращений:

(1)

Для поля ( x, y ) построим последовательность полей

и отберем из них те, для которых

Рис. 2. Схема упорядочивания множества возможных ходов коня

Именно эти поля и составляют множество M(x, y ). Каждому элементу ( a, b) I M(x, y) припишем номер k столбца D , элементы которого в соответствии с (2)-(3) задают приращения по осям для перемещений коня из ( x, y ) в ( a, b ). Таким образом, возможные ходы коня из ( x, y ) упорядочены по полученным ими номерам. На рис.2 эти номера проставлены в соответствующих клетках. Заметим, что иные варианты матрицы D , а всего их 8!=40320, дают иные способы упорядочивания M(x, y).

Решая поставленную задачу с помощью общей схемы 3 перебора с возвратом, мы должны последовательно формировать вектор длины n 2 . Нам удобней строить не вектор, а матрицу размером n ? n , отмечая в её клетках номера ходов коня от единицы и до n 2 . Делать это можно с помощью функций main () и Ktour().

Параметры головной функции main(n, x, y) — это размер доски ( n ) и начальная точка ( x, y ), с которой начинаются перемещения коня. В main () инициируется нулями доска-матрица H размером n ? n и осуществляется первый ход. Далее реализуется обращение к рекурсивной функции Ktour () и после вычислений выводится матрица H с полным туром коня или сообщение об отсутствии решений.

Параметры рекурсивной функции Ktour(n, x, y, H, boo, j) — это размер доски ( n ), точка ( x, y ), с которой осуществляется очередной ход коня, доска ( H ), глубина рекурсивных обращений ( j ) и вспомогательная переменная boo . Функция Ktour () возвращает текущую матрицу H и величину boo , которая равна нулю или единице в зависимости от того, удалось или нет осуществить ход конем в текущем рекурсивном обращении.

В каждом рекурсивном вызове глубины j делается попытка разместить коня в очередное j -е поле доски. Позицию, из которой коня продвинуть дальше нельзя, назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему полю и продолжению работы с ним. Иных случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии, как и в задаче 1, мы должны считать совокупность всех тупиков. Элементы базы заранее до вычислений неизвестны. Если в очередном рекурсивном вызове продвинуть коня удается ( boo =1), то осуществляется переход к следующему рекурсивному вызову. Если удается продвинуть коня на последнюю из незанятых клеток Н, то осуществляются последовательные возвраты на первый рекурсивный уровень ( j =0) и возвращается решение ( H ). Если осуществлен возврат на первый рекурсивный уровень при незаполненной доске и на этом уровне уже испытаны все допустимые ходы, то выдается сообщение об отсутствии решений.

Замечание. Попытки решать задачу 2 при n ? 8 с помощью программ main () и Ktour (), реализованных на языке программирования Mathcad , наталкиваются на сложности, связанные с недостатком памяти или продолжительностью вычислений. Не спасает и реализация этих программ на каких-либо языках программирования компилирующего типа. Незначительное ускорение вычислений может обеспечить переход к нерекурсивному варианту функции Ktour (). Поэтому для решения задачи 2 даже для обычной шахматной доски ( n =8) требуются какие-либо иные подходы. Об одном из них и пойдет речь в следующем пункте.

Н. АВИЛОВ (ст. Егорлыкская Ростовской обл.).

В шахматной математике популярна задача об обходе конем всех клеток шахматной доски 8 x 8,которой с успехом занимался Леонард Эйлер и, возможно, первым решил ее. В письме к Х. Гольдбаху он сообщал: «…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб. Подобное решение представлено на рисунке» (Цитируется по книге: Игнатьев Е. И. В царстве смекалки. — М.: Наука, 1987, с. 81. ).

Письмо датировано 26 апреля 1757 года. Так что можно говорить о 250-летнем юбилее этой задачи, интерес к которой не остывает до сих пор. Задача неоднократно обобщалась — например, разработаны универсальные алгоритмы обходов конем квадратных досок размером n x n , прямоугольных досок размером n x m (см. «Наука и жизнь» № 1, 2003 г.).

В этой статье рассмотрим вопрос об обходе шахматным конем фигурных досок определенного класса. Фигуру, изображенную на рисунке, назовем ступенчатым квадратом. Порядок или размер его определим по числу ступенек на каждой стороне. Например, на рисунке приведен ступенчатый квадрат 8-го порядка.

Оказывается, все клетки ступенчатого квадрата любого порядка можно обойти шахматным конем, побывав в каждой клетке только один раз. На рисунках показаны замкнутые маршруты коня для ступенчатых квадратов 2-го, 3-го и 4-го порядков.

Доказательство этого факта состоит из следующих шагов:

1. Строят замкнутые обходы для пяти базовых фигур. К ним относятся ступенчатые квадраты 2-го, 3-го, 4-го порядков и еще двух фигур, изображенных на рисунке.

2. Обосновывают возможность разбиения ступенчатого квадрата любого порядка на базовые фигуры.

3. Показывают возможность объединения обходов базовых фигур в один замкнутый маршрут.

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

Остается объединить эти маршруты в один. Заметим, что данный ступенчатый квадрат разбит на базовые фигуры двух видов. На рисунке вверху показаны всевозможные пары соседних базовых фигур предложенного разбиения ступенчатого квадрата. В каждой паре выделены красным цветом два звена маршрута, по одному в каждой базовой фигуре. Если эти красные звенья перекинуть как «мостик» на соседнюю фигуру в той же паре, получим замкнутый обход в объединенной паре. Таким образом можно объединить обходы любых двух базовых фигур разбиения в один замкнутый маршрут.

Конечно, нужна стратегия объединения обходов фигур разбиения. В качестве одной из них можно предложить объединение соседних фигур «змейкой», изображенной на рисунке в правой колонке. В результате такого объединения получим замкнутый маршрут шахматного коня по всем клеткам ступенчатого квадрата 8-го порядка.

Подобным методом можно построить маршрут коня для ступенчатых квадратов порядка n = 3 k + 2. Заметим, что предложенный метод почти универсален. Различия возникают при разбиении ступенчатого квадрата на базовые фигуры, а это зависит от его порядка n . Как разбивать ступенчатые квадраты порядка n = 3 k и n = 3 k + 1 на базовые фигуры, показано на следующих рисунках (см. с. 121, 122, 123).

Далее строят обходы для каждой фигуры разбиения (а они все базовые) и «змеевидной» стратегией перекидывания мостиков объединяют в один замкнутый маршрут шахматного коня. Руководствуясь этим алгоритмом, можно построить обходы конем ступенчатых квадратов порядка n = 3 k и n = 3 k + 1.

Это значит, что рассмотренным методом можно построить обход конем клеток ступенчатого квадрата любого порядка. Но на этом задача Эйлера не исчерпала себя. Любознательный читатель может изучить возможность обхода конем клеток, например, ступенчатого прямоугольника. Но это уже другая задача.

нПЦОП МЙ ИПДПН ЛПОС ПВПКФЙ ЧУЕ ЛМЕФЛЙ ЫБИНБФОПК ДПУЛЙ, ОБЮБЧ У ЛМЕФЛЙ Б1, ЪБЛПОЮЙЧ Ч ЛМЕФЛЕ h8 Й ОБ ЛБЦДПК ЛМЕФЛЕ ДПУЛЙ РПВЩЧБЧ ТПЧОП ПДЙО ТБЪ?

рПДУЛБЪЛБ

ъБНЕФШФЕ, РПУМЕ ЛБЦДПЗП ОЕЮЕФОПЗП ИПДБ ЛПОШ ОБИПДЙФУС ОБ ВЕМПК ЛМЕФЛЕ, РПУМЕ ЛБЦДПЗП ЮЕФОПЗП — ОБ ЮЕpОПК.

тЕЫЕОЙЕ

оЕФ, ОЕМШЪС. юФПВЩ ПВПКФЙ ЧУЕ ЛМЕФЛЙ ЫБИНБФОПК ДПУЛЙ, ОБДП УДЕМБФШ 63 ИПДБ. рПУМЕ ЛБЦДПЗП ОЕЮЕФОПЗП ИПДБ ЛПОШ ОБИПДЙФУС Ч ВЕМПК ЛМЕФЛЕ, РПУМЕ ЛБЦДПЗП ЮЕФОПЗП — Ч ЮЕТОПК. ъОБЮЙФ ОБ 63-Н ИПДХ ЛПОШ ПВСЪБФЕМШОП РТЙДЕФ Ч ВЕМХА ЛМЕФЛХ. оП ЛМЕФЛБ h8 — ЮЕТОБС, УМЕДПЧБФЕМШОП, РПУМЕ РПУМЕДОЕЗП ИПДБ Ч ЬФПК ЛМЕФЛЕ ЛПОШ ПЛБЪБФШУС ОЕ НПЦЕФ.

йУФПЮОЙЛЙ Й РТЕГЕДЕОФЩ ЙУРПМШЪПЧБОЙС

ЛТХЦПЛ
нЕУФП РТПЧЕДЕОЙС нгонп
ЛМБУУ
лМБУУ 5
ЗПД
зПД 2004/2005
ЪБОСФЙЕ
оПНЕТ 8
ЪБДБЮБ
оПНЕТ 8.5

рТПЕЛФ ПУХЭЕУФЧМСЕФУС РТЙ РПДДЕТЦЛЕ Й .

Главная ? Инфотека ? Математика ? Книги ? Глава 5. Задача о ходе коня / Математика на шахматной доске // Гик Е. Я.

Комментарии: 0

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

Обойти конем все поля шахматной доски, посетив каждое из них по одному разу.

В литературе эту задачу обычно называют просто задачей о ходе коня. Особая популярность задачи объясняется тем, что в XVIII и XIX вв. ею занимались многие крупные математики, в том числе великий Леонард Эйлер, посвятивший ей большой мемуар «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию»21. Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность, поэтому задачу часто связывают с его именем.

Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня, а в нахождении всех маршрутов и подсчете их числа. Увы, эта задача не решена до сих пор, и шансов на успех немного. Известно, правда, что число решений не превосходит C 63 168 (это число состоит из ста цифр), но больше 30 миллионов. Математик Ф. Миндинг, подошедший к проблеме с алгебраической точки зрения, предложил метод, позволяющий вывести формулу для числа всех решений, однако вычисления, которые следует при этом произвести, практически неосуществимы, и поэтому метод Миндинга представляет лишь теоретический интерес.

Литература, посвященная задаче о ходе коня, весьма обширна. Те или иные методы нахождения маршрутов можно найти в самых разнообразных источниках. Среди них следует выделить книгу Крайчика «Проблема коня», которая, как видно из названия, целиком посвящена этой теме (эта книга входит в упомянутую во введении фундаментальную работу Крайчика). Об алгебраическом подходе, основанном на исследованиях Янишад рассказывается у Окунева, а у Шуберта22 можно найти подробный исторический обзор задачи о ходе коня. Остановимся на некоторых наиболее интересных методах нахождения маршрутов коня.

Рамочный метод Мунка и Коллини. (Коллини — секретарь знаменитого философа Вольтера). Шахматную доску разделим па две части: внутреннюю, состоящую из 16 полей, и внешнюю, имеющую форму рамы и состоящую из 48 полей (рис. 23,а). На полях внутреннего квадрата запишем заглавные буквы А, В, С, D — так, чтобы каждая из них, повторенная четыре раза, образовала квадрат или ромб, по всем сторонам которого может ходить конь. Те же буквы, только строчные, запишем на рамочных полях так, чтобы ходы коня по каждой из букв образовали замкнутые многоугольники, окаймляющие центральный квадрат.

Конь начинает ходить от какого-нибудь рамочного поля, проходит вокруг рамы по выбранной букве, например а, и в 12 ходов исчерпывает эту букву (при этом последнее поле не должно быть угловым). Затем он переходит во внутренний квадрат, но не на букву Л, а на какую-нибудь другую — В, С или D. Пройдя все поля, обозначенные этой буквой, конь снова переходит на раму — на букву, по которой еще не ходил, и вновь обегает вокруг рамы, исчерпывая до конца эту букву, — и т. д., пока не пройдет по всей доске.

Метод Полиньяка и Роже — деление на четверти. Этот метод проще предыдущего, хотя и похож на него. Разделим доску крестом на четыре квадрата (рис. 23,б). В каждом из них расставим буквы а, b, с, d точно так же, как во внутреннем квадрате на рис. 23,а. Конь начинает движение с любой буквы, проходит в выбранном квадрате по всем четырем полям с этой буквой, затем переходит на ту же букву соседнего квадрата, и т. д. Исчерпав все 16 полей с одной буквой, он меняет ее и снова зигзагом обегает доску. После четырех таких кругов все поля будут пройдены (как и в предыдущем методе, «круговые» маневры не должны заканчиваться на угловом поле).

Маршруты и пути коня по доске удобно нумеровать последовательными числами 1, 2, 3 … в соответствии с порядком ходов. В полном маршруте коня начальное поле имеет номер 1, а конечное — 64. Разумеется, изменив направление данного маршрута на противоположное, мы всегда можем начальное поле сделать конечным, и наоборот. Если маршрут замкнут, то поля 1 и 64 связаны ходом коня.

Метод Эйлера и Вандермонда. Этот метод, хотя и не является таким простым и эффектным, как два предыдущих, позволяет, в отличие от них, получать самые разнообразные маршруты коня.

В основе метода лежит возможность замены обратными всех ходов, начиная с поля, связанного ходом коня с конечным.

В качестве примера рассмотрим маршрут на рисунке 24, а. Используя связь поля 31 с конечным полем 64, мы можем получить еще один маршрут. Оставим все числа 1, …, 31 на своих местах, а числа 32, 33, …, 64 заменим соответственно числами 64, 63, …, 32. Иначе говоря, один последовательный путь (от поля 32 до поля 64) мы заменили другим, обратным (от 64 до 32). Теперь поле b4, поменявшее номер 32 на 64, стало конечным. Новый маршрут в старой нумерации полей можно записать так: от 1 до 31, 31 — 64 (один ход — с поля 31 на 64), от 64 до 32.

Указанный прием можно повторять многократно, получая все новые и новые маршруты. В исходном маршруте поле 49 также связано с 64, что дает нам другой производный маршрут: от 1 до 49, 49 — 64, от 64 до 50. В первом из найденных маршрутов поле 32 связано с 43 — и мы можем получить второй производный маршрут: от 1 до 31, 31 — 64, от 64 до 43, 43 — 32, от 32 до 42, и т. д.

Если дан некоторый маршрут, то, проявив определенную изобретательность, его можно преобразовать так, чтобы любое наперед заданное поле стало конечным (а эначит, и начальным). Пусть, например, мы хотим сделать конечным поле d4, имеющее номер 56. Свяжем его с полем 64 такими ходами: 64 — 31 — 32 — 57 — 56. Теперь дважды преобразуем исходный маршрут коня (рис. 24,а): 1) от 1 до 31, 31 — 64, от 64 до 32; 2) от 1 до 31, 31 — 64, от 64 до 57, 57 — 32, от 32 до 56. Последний маршрут заканчивается на поле d4, к чему мы и стремились. Описанным методом из незамкнутого маршрута иногда удается получить замкнутый. Так, для превращения маршрута на рис. 24,а в замкнутый достаточно пути: от 11 до 17, от 10 до 1, от 18 до 31, от 64 до 57, от 32 до 45, от 56 до 46 заменить соответственно такими: от 1 до 7, от 8 до 17, от 18 до 31, от 32 до 39, от 40 до 53, от 54 до 64.

Основное достоинство метода Эйлера и Вандермонда заключается в том, что он помогает нам завершить путь коня в тех случаях, когда мы двигались без всякой системы и попали в тупик — дальше идти некуда, а еще остались непройденные поля. Пусть, например, мы уже побывали на 62 полях доски (путь от 1 до 62 на рис. 24,б, а поля а и b не посетили). Здесь поле а связано с полем 10, а поле 62 с полем 9. Это позволяет нам преобразовать путь от 1 до 62 в следующий: от 1 до 9, 9 — 62, от 62 до 10. После перенумерации поле b2 в этом пути меняет номер 10 на 62 и под номером 63 к пути присоединяется поле а. Теперь нам осталось присоединить к пути поле b. В этом нам помогает то обстоятельство, что из двух последовательных полей 57 и 58 первое связано с полем b, а второе — с полем а (имеющим сейчас номер 63). Теперь наш путь (в исходной нумерации) превращается в такой: от 1 до 9, 9 — 62, от 62 до 58, 58 — а, а — 10, 10 — 57. После очередной перенумерации номер 63 теперь получает бывшее поле 57, и, присоединяя к нему поле b, получаем, наконец, искомый маршрут (рис. 24,а; нумерация здесь последовательная — от 1 до 64).

Рассмотренные нами преобразования — далеко не единственные, позволяющие получать из одних маршрутов другие. Упомянем еще преобразования, связанные с поворотами доски и отражениями ее относительно осей симметрии или центра симметрии. Различные свойства маршрутов, основанные на идеях симметрии, исследованы в указанной ранее литературе. Заметим, кстати, что из одного замкнутого маршрута коня можно получить сразу 127 новых: 63 — сдвигом нумерации ходов, а из полученных 64 — еще столько же изменением направления маршрута.

Правило Варнсдорфа. Это довольно эффективное правило заключается в следующем.

1) при обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; 2) если таких полей несколько, то разрешается выбирать любое из них.

Правило Варнсдорфа предложено более 150 лет назад. Долгое время считалось, что оно действует безукоризненно. Позднее было установлено, что его вторая часть не совсем точна. Если в распоряжении коня имеется несколько возможностей, упомянутых в первой части правила, то не все они являются равноценными. Полную яспость в этот вопрос удалось внести при помощи ЭВМ. Машинный эксперимент, проведенный в Тульском пединституте под руководством А. Есаяна, показал, что с какого бы поля доски конь ни начал свой маршрут, можно так пользоваться второй частью правила Варнсдорфа, что он попадет в тупик раньше, чем посетит все поля доски.

Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.

Правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

На практике это реализуется, например, следующим образом. Перед каждым ходом коня вычисляется рейтинг ближайших доступных полей — полей, на которых конь еще не был, и на которые он может перейти за один ход. Рейтинг поля определяется числом ближайших доступных с него полей. Чем меньше рейтинг, тем он лучше. Потом делается ход на поле с наименьшим рейтингом (на любое из таковых, если их несколько), и так далее, пока есть куда ходить.

Эвристика всегда работает на досках от 5×5 до 76×76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

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


Переборное решение

Другой способ решения задачи, состоит, очевидно, в переборе с отходом назад. Ниже дана иллюстрация подхода для доски 8×8.

Используем два одномерных массива row[64] и col[64] для хранения соответственно номеров строк и колонок, которые конь последовательно проходит по доске.

Конь, находящийся в позиции (i, j), может следующим ходом оказаться в клетках с координатами (i-2, j+1), (i-1, j+2), (i+1, j+2), (i+2, ,j+1), (i+2, ,j-1), (i+1, j-2), (i-1, j-2), (i-2, j-1). Заметим, что если конь находится вблизи края доски, то некоторые ходы могут вызвать перемещение коня за ее пределы, что, конечно же, недопустимо. Восемь возможных перемещений коня могут быть заданы в виде двух массивов ktmov1[] и ktmov2[], как продемонстрировано в следующем фрагменте программы.

Исходя из этого, конь, находящийся в позиции (i, j) может переместиться в позицию (i+ktmov[k], j+ktmov2[k]), где k — какое-либо значение из диапазона 0 — 7, выбираемое из условия, что конь должен остаться на доске. Итак, программа, реализующая перемещение коня в соответствии с вышеприведенными условиями будет выглядеть следующим образом:

Составить программу, в соответствии с которой шахматный конь обойдет всю доску, побывав на каждом поле всего один раз.

Делимся мнением, господа.

06.06.2016, 22:37

Обойти шахматным конем все клетки шахматной доски, побывав на каждой клетке по одному разу
Здравствуйте, помогите пожалуйста Рекурсия, нужно обойти шахматным конем все клетки шахматной.

Обойти шахматное поле конем побывав в каждой клетке не более одного раза
Помогите, пожалуйста, решить задачу: необходимо обойти шахматное поле конем побывав в каждой клетке.

Есть острова и мосты между ними. Нужно обойти все острова, побывав на каждом мосту по разу
Задача «Острова и мосты» (задача Эйлера). Есть острова и мосты между ними. Нужно обойти все.

Обход доски шахматным конем
решал задачу «Тур конем». : На шахматной доске размером n*n на поле с координатами x0,y0 находится.

07.06.2016, 06:03 2

Простейшая задача.
Решается методом перебора.
Можно использовать рекурсию.

К примеру, для размера поля 5×5 и начальной позицией 3х3 будет 64 решения.
А для начальной позиции 1х1 поля того же размера уникальных решений будет 304.

08.06.2016, 13:55 3
08.06.2016, 13:55
08.06.2016, 13:55

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Написать программу, реализующую обход доски шахматным конём
Конь находится в клетке (x1,y1).Нужно вывести любой его путь из (x1,y1) в (x2,y2).Если это.

Составить программу обхода шахматным конем шахматной доски по всем клеткам
Составить программу обхода шахматным конем шахматной доски по всем клеткам, не побывав на каждой.

Попасть шахматным конем в заданную клетку поля за наименьшее число ходов
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку.

В квадрате 4х4 расположить 16 букв, чтобы в каждом горизонтальном и каждом вертикальном ряду буква встречалась только один раз
В квадраті 4х4 розташувати 16 літер (чотири a, чотири b, чотири c, чотири d) так, щоб в кожному.

Это, пожалуй, самая известная шахматная задача. Заключается в том, что бы обойти конем шахматную доску(буквой «Г»), наступив на каждую клетку только один раз.

Знаменитый математик Эйлер посвятил этой задаче большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию».

Существуют замкнутые решения (последний ход коня заканчивается в одном ходе от начала) и незамкнутые решения.

Для шахматной доски размером 8 х 8 существует:

— 26,534,728,821,064 вариантов замкнутых решений

— 19,591,828,170,979,904 вариантов незамкнутых решений

Для квадратных досок N x N решение существует для всех N>=5

Многие наверное играли на бумаге в эту игру, кто не пробовал — попробуйте. На листочке в клетку 10 на 10 (можно любой размерности от 5) ставим цифры ходом коня, пока не заполним все поле. Довольно увлекательно можно было коротать какие-то скучные моменты в школе.

Найти одно из решений можно по правилу Варнсдорфа. Звучит оно так:

При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них.

С этим правилом решать такие задачи стало намного проще. Поэтому я решил написать игру немного усложнив правила. Игра под андроид называется Ход Конем.

Кому интересно напишите в комментариях, сделаю отдельный пост про неё, так как понимаю, что рекламу тут не любят)

Есть довольно интересные решения этой математической задачи. Например, есть решение, которое образует так называемый полумагический квадрат. Магический квадрат — квадратная таблица N x N, заполненная различными числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях одинакова.

Полумагический он только потому, что сумма чисел по диагоналям разная. Зато есть другие особенности:

Вот еще интересная, но уже 3D визуализация решения для поля 8 x 8 x 8:

Спасибо за внимание!

Найдены дубликаты

Вот буквально сегодня вечером решил вспомнить про эту игру, нарисовал квадрат 10х10, и споткнулся (как всегда) на 97. ЗАхожу на пикабу, вижу твой пост.

Для шахматной доски размером 8 х 8 существует:

— 26,534,728,821,064 вариантов замкнутых решений
— 19,591,828,170,979,904 вариантов незамкнутых решений

Для доски 10х10 полагаю существует еще больше. Так какого ж блин хрена при всех этих квадриллионах решений у меня не получается даже одного -___-

неужели я настолько тупой -__-

а всего вариантов ходов, даже незаконченных немыслимо много. Не знаю сколько для хода коня, но число всех комбинаций шахматных партий

10^120 степени. Для сравнения атомов во вселенной только

10^80. Так что все нормально) Пробуй с 5 на 5

Хм. а как именно было точно подсчитано количество всех комбинаций? Мне просто интересна сама методика в целом, не нужно километры формул и тонны пикселей-цифр -)

это так называемое число Шеннона

Вряд ли формулы сложные. Наверняка использовалась комбинаторика. В ней самое сложное понять куда какую формулу применить

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

Скинул друг однажды задачу про коня и 10х10. Говорит просидел над ней часов 5, но решить не смог. Я за минуты 2 нашел одно из квадриллиона решений)

Сначала попытался заполнить 5×5, а потом просто переворачивал этот квадрат и заполнял таблицу)

Вот буквально сегодня вечером решил вспомнить про эту игру

Эффект Майнкрафта-Киберскотча, не иначе.

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

выиграл одноклассник, а потом назвал её «ход конём»

Тоже неплохо было бы реализовать её вам как компьютерную игру

а ты поищи в плеймаркете по запросу «ход конем»

Уже ни названия, ни каких опознавательных знаков не вспомню. Разве что правила «начинаем в одном углу, заканчиваем в другом» я не помню. Просто проигрывает тот, кто не может сделать ход.

есть еще тема: у одного игрока все шахматные фигуры, а у второго только одна, но это фигура совмещает в себе ферзя и коня, соотвественно задача одного съесть эту фигуру, а другого поставить мат. По-моему называлась «магараджа».

Не знал о таком варианте, спсибо

Все больше и больше разрастается вопрос: есть ли вообще хоть что нибудь математическое, к чему не приложился бы Эйлер?!

Одна из задач, задаваемая для понимания рекурсивного метода решений и кстати, именно она шикарно поясняет до какой глубины рекурсии данный метод является эффективным.

не понял но плюсанул . Шикарно, очень весьма шикарно

мне в школе одноклассник эту задачу показал, я 1й раз 98 клеток заполнил, а потом уже отдельно мелкий квадрат который было сложно заполнить полностью — заполнял отдельно в несколько попыток на черновиках и в итоге на чистовике 100 клеток заполнил, но схема была другой о_0 сначала по стенке ходил конём — 2 полосы заполнив и потом уже внутренний квадрат думал отдельно как заполнить

ну да, почему не минусануть бы человека — который поделился воспоминаниями >_

Графика симпатичная, сам рисовал или фрилансеры? 🙂

графику художник рисовал, не я

Наёмный или знакомый?

У меня была серия похожих головоломок, вернее эта была одна из них.

Но графика была покондовее, сам в угаре рисовал 🙂

«Игры Разума» называлась игруха.

это та, где чтобы начать игру нужно один цвет для всей картины подобрать?

Да, только не любой — а нормальный.

пыталась я пройти ее. Только видимо слишком я тупенькая для нее, на игре с шариками слилась. уж не помню какой уровень

:)) Много кто не смог, на то и расчет был.

Спасибо тебе большое. Крутая игра была. Ее сейчас можно где-то скачать?

Да конечно, по прежнему в во всех сторах страны 🙂

:))) Можно было нажать на кнопку сбросить 100 раз и уровень пропускался 😉

Художник наёмный. А где игра сейчас, почему была?

Ну сейчас она есть, просто далеко не в топах. Уже отыграла в свое время.

музыка в видео вызывает какие-то жуткие ощущения.

Это музыка из известной в свое время игрушки 7th Guest, 11th Hour,

с ней вообще вышло интересно — мне недавно написал автор этой музыки George Sanger (The Fat Man), типа я спер музыку. Ну собственно я и спер, нашел в инете. 🙂 Но мужик классный оказался, пообщались — он разрешил использовать.

Стащи у Киркорова :))

Я могу поставить слово «классный» в одном контексте с Киркоровым, если будет придано обратное значение слову «классный» каким-нибудь «нифига не классный он мужик».

Или же в таком «Классный был выстрел в голову Киркорову, он прям засиял»

10-50млн инсталлов. неплохо ) начальный трафик покупал? или само вылезло в топ?

Разговор с копипастой?

В школе играли, но квадрат был не 8х8, а 10х10. Научился закрывать все клетки, проходя конем с одно угла, постепенно углубляясь к центру, как то так.

Не будут же в правилах писать «буквой Г».

на две клетки по горизонтали или вертикали, затем на одну клетку по вертикали или горизонтали

Я не знаю о какой высшей математике идет речь, но будучи студентом не раз заполнял все поле на скучных парах, и не я один, там общий принцип довольно быстро допираешь методом тыка.

При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них.

Насколько я помню, если в случае неопределенности ходить на поле, которое ближе к краю, то получается еще сильней увеличить максимальный размер доски (что-то типа с 100 до 300).

Такая задача была в игрушке «Последняя воля Шерлока Холмса», и если ошибался с ходом, Шерлок говорил «не правильно, нужно начать всё заново». заново. заново.

неее. не реклама)

Что там решать, конём ходи!

С математиками амщемто скучно, особенно с физиками они тебе теорию, а ты им еще её и доказывай!

А с Пикабу , что ли проще?! Тут тоже чуть что сразу пруфы требуют.

Ты гонишь. ну ка пруф покаж что пруфы требуют!

Задача про фермера по математике

Пока карантин учитель дал всем в классе задание пройти математический конкурс, который проводит факультет математики местного универа.

Чтоб было проще проверять я для себя прорешал задачки. Благо 5-ый класс я еще могу осилить 🙂

Заинтересовала вот эта задача:

Заинтересовала тем, что я ее решил составив систему уравнений с двумя неизвестными.

Уравнения не сложные. Решить легко. Одно неизвестное выразил из второго, подставил , посчитал, подставил обратно — готово. Мешок моркови = 20 кг, гороха = 15 кг.

НО они в 5-м классе еще НЕ проходили уравнения с двумя неизвестными.

Думаю нафига такое давать детям, придется опять за учителя работать, объяснить суть таких уравнений, чтобы у нее получилось решить.

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

Возвращаюсь через 5 минут, а дочка говорит что решила. Дает ответ 100 кг. — правильно, у меня также получилось.

Удивляюсь. Не ожидал. Думал она составит эти уравнения и дальше дело у нее не пойдет, а тут правильный ответ. Я ее дольше решал.

Спрашиваю: «Когда вы системы уравнений успели пройти?» — она вообще не в курсе что это такое 🙂 и показывает решение. А там все до гениального просто. Нужно только быть внимательным при прочтении условия задачи.

В условии пункт «А). 3 мешка моркови и 2 куля гороха весят столько же, сколько 9 мешков картофеля«. Потом говорится, что «Один мешок картошки весит 10 килограмм«

И сам вопрос «Сколько килограмм вместе весят 3 мешка моркови, 2 куля гороха и 1 мешок картошки?«

У меня в голове сразу уравнения начали складываться, а не затуманенный этой белибердой детский мозг увидел, что там все проще простого.

Дочь говорит: «Смотри в пункте А) сказано все тоже самое, что и нужно узнать, только + еще 1 мешок картошки, который тоже дано сколько весит» .

ВСЕ, для решения задачи данные пункта Б) даже не нужны

1 мешок картошки = 10 кг. по условию, а 3 мешка моркови и 2 гороха весят как 9 мешков картошки = 90 кг. опять таки по условию пункта А).

Просто и гениально.

Сказал что будет свой вариант решения писать, а не эти непонятные уравнения.

Хорошая задача для подготовки к ЕГЭ по математике

Иван Иванович — псих. И ему срочно нужны деньги. Поэтому он собрался туда, где деньги дадут быстро и безо всяких проблем. Выбор его пал на ЗАО «Быстроденьги». И ему дали кредит на 6 лет под 50%.

Все 6 лет Иван Иванович и его жена жили, затянув пояса. Под конец, она решила спросить, ради какой суммы они столько терпели. Он ушёл от ответа, сказав, что переплата составила 3.044.000 рублей. Помогите супруге узнать сумму, взятую в кредит.

кредит гасится каждый год равными платежами. 50% — годовых

Странная задача

Готовлю одного из своих учеников (четвертый класс) к олимпиаде по математике. В заданиях прошлых лет нашел очень неоднозначную задачу.

Али-Баба каждый месяц откладывает некоторое постоянное количество золотых монет на постройку дворца. Он подсчитал, что если будет каждый месяц откладывать на 17 монет больше, то сможет построить дворец уже через 5 лет, а если только на 16 монет больше — то через 10 лет. Через сколько лет Али-Баба сможет построить дворец, если продолжит откладывать каждый месяц прежнее количество золотых монет?

Самое интересное, что к этой задаче есть и ответ, и решение. Внезапно.

А можно Ваше мнение по поводу этой задачи, уважаемые математики Пикабу?

Репетиторские истории #22: бабушка

У одного моего ученика (Репетиторские истории #20: Шелдон) есть бабушка.

Причем, она проявляет даже больше активности в вопросах, касающихся наших занятий с мальчиком, чем мама.

Ну, это касается именно взаимодействия со мной. Как у них в семье это происходит, меня не касается.

Так вот, мальчика готовлю к поступлению в лицей. Пока остановились на трёх вариантах (школа 57, школа «интеллектуал» и школа 1580 при МГТУ им. Баумана).

Уровень задач на поступление очень приличный, несмотря на то, что прием идёт в 5-ый класс.

Дети в 4-ом классе, где как раз учится этот мальчик, только начали в столбик считать. Даже не представляю, как ему там скучно среди остальных, которые умудряются и там жаловаться на тяжесть обучения.

Так вот, чтобы подготовить мальчика к решению задач подобного уровня, нахожу ему множество нестандартных и очень тяжёлых задач, от которых даже средние восьмилассники будут пускать слюни.

Возможно, как-нибудь и сюда скину несколько подобных задач:)

Так вот, речь о бабушке.

Как оказалось, эта забава с решениями интересных задачек пришлась и ей по вкусу.

Каждый раз, когда прихожу на занятие, бабушка выбегает к порогу с исписанными листиками и говорит: «А я тоже решала задачки, посмотрите, пожалуйста, правильно ли всё?».

И я проверяю:) И если всё правильно, она аж цветет от счастья.

Говорит: «До чего же это всё интересно! Обожаю решать задачки. Да и поможет не так скоро с дедушкой Альцгеймером встретиться».

Так что я веду занятия не только у мальчика, но и бабушки:)

admin