01 февраля 2020

Задача о беглеце

Пишу, перевожу и иллюстрирую IT-статьи. На proglib написал 140 материалов. Увлекаюсь Python, вебом и Data Science. Открыт к диалогу – ссылки на соцсети и мессенджеры: https://matyushkin.github.io/links/ Для отправки опечаток на десктопе выделите текст и нажмите [Ctrl]+[Enter]. Если понравился стиль изложения, упорядоченный список публикаций и курсов — на GitHub: https://github.com/matyushkin/lessons
Новая головоломка о спасении заключённого и подробно иллюстрированный ответ на решение задачи о шести шахматных конях.
Задача о беглеце

Условие задачи о беглеце

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

Решение – в следущей задаче.

Эта задача – десятый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую головоломку о шести шахматных конях.

***

Решение задачи о шести шахматных конях

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

Ответ: Минимальное количество ходов, необходимое для решения головоломки (с учётом указанной оговорки), составляет 16.

Решение. Начальное состояние удобно представить в виде графа, как на рисунке ниже. Цвет добавлен, чтобы было проще понять связи между полями. Линии соединяют те позиции, между которыми может двигаться фигура коня.

Задача о беглеце

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

Задача о беглеце

Распутываем граф. Узлы 8 и 5 в сравнении с исходной картинкой мы переместили соответственно вверх и вниз. Узлы 4 и 6 поменяли местами, чтобы получить второй рисунок. Затем обменяли узлы 10 и 12, получили третье представление. Наконец, то же сделали с узлами 11 и 2. Показали где исходно находятся белые и чёрные фигуры. Теперь у нас есть развёрнутое представление графа.

Ходы чёрных. Чтобы достичь цели головоломки, один из двух чёрных коней в начальных позициях 1 или 3 должен переместиться в 12 или 10. Пусть конь в позиции 1 перемещается в 12, что ближе к его исходной позиции, чем позиция 10. По кратчайшему пути потребуется 3 хода (1 – 6 – 7 – 12). Другим двум чёрным коням понадобятся в сумме как минимум 4 хода, чтобы добраться от позиций 2 и 3 к позициям 10 и 11 (например, 2 – 9 – 10 и 3 – 4 – 11).

А белые кони? Симметрия подразумевает одинаковую нижнюю границу из 7 ходов для белых коней. Таким образом, головоломка не может быть решена менее чем за 14 ходов. Но задачу нельзя решить ни за 14, ни за 15 ходов. Это связано с блокировками фигур противоположного цвета и можно доказать от противного.

Доказательство. Для удобства далее будем обозначать чёрных коней – Ч, белых коней – Б. Предположим, что существует последовательность ходов, которая решает головоломку менее, чем за 16 ходов. В такой последовательности Ч1 должен будет достичь поля 12 за 3 хода, потому что он не может сделать это за 4 хода. А если сделает за 5 или более ходов, общее их количество будет уже не менее (5 + 4) + 7 = 16.

Но прежде чем Ч1 сможет перейти с 6 на 7, должны произойти ходы

  • Б(12 – 7 – 2), этому должно предшествовать
  • Ч(2 – 9), этому предшествует
  • Б(10 – 9 –4), этому предшествует
  • Ч(3 – 4 – 11), этому предшествует
  • Б(11 – 6).

Но такой ход блокирует Ч1, и таким образом, необходимое количество ходов превышает 15.

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

  • Ч(1 − 6 − 7)
  • Б(11 − 6 − 1)
  • Ч(3 − 4 − 11)
  • Б(10 − 9 − 4 − 3)
  • Ч(2 − 9 − 10)
  • Ч(7 − 6)
  • Б(12 − 7 − 2)
  • Ч(6 − 7 − 12)

Соответствующее решение мы изобразили на рисунке.

Задача о беглеце

Как ответили читатели Библиотеки программиста? В первую очередь мы рассматриваем ответы на сайте. Читатель Sansss предложил решение (с учётом указанной выше оговорки) за 18 ходов, то есть чуть больше, чем получилось у нас:

За 18 ходов точно можно переместить фигуры. 12 – 7 7 – 6 1 – 8 6 – 1 2 – 7 7 – 12 10 – 9 9 – 2 3 – 4 4 – 9 9 – 10 8 – 3 3 – 4 4 – 9 11 – 4 4 – 3 9 – 4 4 – 11
Задача о беглеце

Читатель Bodya.Net привёл решение с учётом более жёсткого ограничения на чередование ходов чёрных и белых. Распутанный граф вышел таким же, как у нас. Получилось 22 хода, правда не описана строгая последовательность движения чёрных и белых по отдельности.

Начертил граф, если соблюдать правила (чередовать ходы черных и белых), получается, что каждому стороне нужно 11 шагов. Т.е. 22 хода. Я просто по этому графу веду черные фигуры по верху, а белые по низу. 1 – 8 – 3 – 4 – 11 2 – 9 – 10 – 5 – 12 3 – 4 – 9 – 10 10 – 5 – 7 – 2 11 – 6 – 1- 8 – 3 12 – 7 – 6 – 1 Наверное есть более короткие пути, но я их не нашел.
Задача о беглеце

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

16 ходов, стрелками с римскими цифрами обозначены направление и номер хода, справа от рисунка последовательность ходов, в скобках указано кол-во шагов
Задача о беглеце

А Дмитрий Шелухин привёл доказательство о минимальном количестве ходов:

«Можно даже доказать, что 16 это минимальное количество ходов (Min):

1. Min>=14, это уже известно

2. Min !=14. С учетом симметрии, есть 2 разных потенциальных способа за 14 ходов решить задачу: когда центры идут в противоположные углы (1, 12) или когда они идут в углы с одной стороны (1, 10). В первом случае сразу находится блокировка (на пути 1-6-11), во втором получается циклическая зависимость (прежде чем сдвинуть коня из 11 нужно ... убрать коня из 11), т.е. тоже кони блокируют друг друга

3. Для того, чтобы переставить 3 коней с одной стороны на другую требуется всегда нечетное число ходов. Какой бы ни оказалась перестановка ((1, 2, 3) -> (12, 11, 10), например) сумма минимальных расстояний всегда будет нечетной. Т.к. в графе только четные циклы, то даже если расстояния будут неминимальными, их четность не изменится. Раз надо переставить 6 коней, то ответ всегда будет четным».

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Team Lead | CTO
от 300000 RUB до 450000 RUB
Software Engineer (C/C++)
Санкт-Петербург, по итогам собеседования
Юнити-разработчик
Москва, от 60000 RUB до 188000 RUB

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ