Задача о ходе коня
Это, пожалуй, самая известная шахматная задача. Заключается в том, что бы обойти конем шахматную доску(буквой "Г"), наступив на каждую клетку только один раз.
Знаменитый математик Эйлер посвятил этой задаче большую работу "Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию".
Существуют замкнутые решения (последний ход коня заканчивается в одном ходе от начала) и незамкнутые решения.
Для шахматной доски размером 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:
Спасибо за внимание!
