Решить
Решатель «Ханойской башни»
Кратчайшее решение для любой допустимой позиции, а не только для полной стопки. Расставьте диски так, как они стоят сейчас, и посмотрите, как играется оптимальный путь.
Оптимальное решение
31ход25 − 1 = 31
Классическая головоломка: все диски начинают на башне A и заканчивают на башне C.
Готово к проигрываниюШаг 0 из 31
←→шагПробелпускHomeEndк краю
Все ходы по порядку
Диск 1 — самый маленький, а A → C означает: снять верхний диск с башни A и положить его на башню C. Выберите любую строку, чтобы перевести поле к этому ходу.
Ход 16 — это диск 5, переходящий с A на C. Ходы по обе стороны от него (по 15 с каждой) — одно и то же решение дважды: решение для меньшей башни (дисков: 4), сыгранное сначала на вспомогательную башню, а потом с неё.
| # | Диск | Откуда | Куда |
|---|---|---|---|
| 1 | 1 | A | C |
| 2 | 2 | A | B |
| 3 | 1 | C | B |
| 4 | 3 | A | C |
| 5 | 1 | B | A |
| 6 | 2 | B | C |
| 7 | 1 | A | C |
| 8 | 4 | A | B |
| 9 | 1 | C | B |
| 10 | 2 | C | A |
| 11 | 1 | B | A |
| 12 | 3 | C | B |
| 13 | 1 | A | C |
| 14 | 2 | A | B |
| 15 | 1 | C | B |
| 16 | 5 | A | C |
| 17 | 1 | B | A |
| 18 | 2 | B | C |
| 19 | 1 | A | C |
| 20 | 3 | B | A |
| 21 | 1 | C | B |
| 22 | 2 | C | A |
| 23 | 1 | B | A |
| 24 | 4 | B | C |
| 25 | 1 | A | C |
| 26 | 2 | A | B |
| 27 | 1 | C | B |
| 28 | 3 | A | C |
| 29 | 1 | B | A |
| 30 | 2 | B | C |
| 31 | 1 | A | C |
На этой странице
Как работает решатель
Метод — это логика самой головоломки, проигранная вперёд. Чтобы посадить самый большой диск на целевую башню, все меньшие диски должны быть где-то ещё, а именно собраны на единственной оставшейся башне. Поэтому решатель сначала требует перенести туда эту меньшую стопку, переводит большой диск и затем требует вернуть меньшую стопку поверх него. Каждое из этих требований — та же задача с одним диском меньше, и так до единственного диска, который перемещается за один шаг.
От решателей, которые умеют работать только с полной стопкой, его отличает одна лишняя строчка рассуждения: если самый большой диск уже на своей целевой башне, с ним делать нечего, и вся задача сводится к дискам над ним. Именно этот случай позволяет решать с наполовину сыгранного поля, а не заставлять начинать заново, — и поэтому число ходов из своей позиции меньше, чем 2ⁿ − 1, а в начатой партии часто намного меньше.
Перенесите n−1 дисков над ним на вспомогательную башню. Пока они не убраны, ничего другого сделать нельзя.
Самый большой диск теперь свободен, а его целевая башня пуста. Он переходит за один ход — единственный, который нужен на этом этапе.
Соберите на нём заново стопку из n−1 дисков. Это та же задача с одним диском меньше — и так до одного диска, который перемещается за один ход.
Как читать решение
Каждая строка называет один ход: какой диск, с какой башни он уходит и на какую ложится. Диск 1 — самый маленький. Проверять допустимость не нужно: любой ход в списке допустим по построению.
Из полной стопки сразу видны две закономерности:
- Самый маленький диск ходит через раз — ходы 1, 3, 5 и так далее — и всегда обходит три башни в одну и ту же сторону.
- Каждый ход между ними — единственный допустимый ход, не трогающий самый маленький диск.
Это и есть весь итеративный метод, и его можно прочитать прямо по любому решению из полной стопки. Из своей позиции список по-прежнему кратчайший, но он сшит из меньших переносов, поэтому самый маленький диск может на полпути сменить направление. Итеративное решение показывает, почему метод работает, а страница стратегий превращает его в то, по чему можно играть. Саму рекурсию, разобранную построчно на шести языках, смотрите на странице алгоритма «Ханойской башни».
У самых частых размеров есть и своя страница, со всеми ходами и тем, что особенного именно в этом размере: решения от 3 до 10 дисков и 64 диска легенды.
Забрать решение с собой
Адресная строка всегда описывает поле на экране. Полный перенос выглядит как ?disks=5&from=A&to=C; своя позиция добавляет код вида pos=CBBAA — по букве на диск, начиная с самого маленького. Скопируйте эту ссылку, и она откроет ровно эту головоломку. Так же можно отправить кому-нибудь позицию, в которой вы застряли, вместо её описания словами.
Сам список ходов копируется в буфер обмена, а ещё скачивается текстовым файлом, чтобы читать его рядом с настоящей головоломкой, и таблицей CSV, чтобы открыть в редакторе таблиц. У скачивания нет предела, который есть у печатаемой таблицы: при пятнадцати дисках в файле по-прежнему все 32 767 ходов.
Почему список кончается на 12 дисках
Решения удваиваются с каждым диском. Двенадцать дисков — это 4 095 ходов, длинная, но пригодная таблица. Тринадцать — 8 191, двадцать — 1 048 575, и ни один браузер не превратит таблицу в миллион строк во что-то, чем можно пользоваться. Выше двенадцати дисков страница даёт точное число ходов и сохраняет анимированное поле, а в скачиваемых файлах выше по-прежнему все ходы: решение остаётся вашим, просто оно не печатается. Если нужны только числа, калькулятор считает до шестидесяти четырёх дисков и дальше.
Частые вопросы
Что делает решатель «Ханойской башни»?
Он выводит кратчайшую возможную последовательность ходов, которая собирает все диски на одной башне. Дайте ему число дисков — он решит классический полный перенос; дайте недоигранную позицию — он решит с неё, а этого большинство решателей не умеет.
Это точно кратчайшее решение?
Да. Решатель не просто верен, а доказуемо оптимален: из полной начальной стопки он выдаёт ровно 2ⁿ − 1 ходов, а из любой другой допустимой позиции — настоящий кратчайший путь к цели. Последовательности короче не существует.
Можно решить с позиции, которую я уже начал?
Да, для этого и нужна своя начальная позиция. Поставьте каждый диск на ту башню, где он стоит сейчас, и решатель доведёт партию до конца за наименьшее возможное отсюда число ходов — обычно оно намного меньше, чем начинать заново.
Можно поделиться решением или сохранить его?
Да. В адресной строке всегда лежит то поле, которое вы видите: /ru/solver/?disks=5&from=A&to=C — это полный перенос пяти дисков, а своя позиция добавляет код вида pos=CBBAA, по букве на диск, начиная с самого маленького. Скопируйте ссылку — и она откроет ровно эту головоломку.
Можно ли скачать список ходов?
Да — простым файлом .txt или таблицей .csv со строкой на каждый ход, рядом с кнопкой копирования. Скачивание работает и для очень длинных решений, которые страница не печатает таблицей, так что ответ для 15 дисков тоже остаётся у вас.
Как читать список ходов?
Каждая строка называет один ход: номер диска, башню, с которой он уходит, и башню, на которую ложится. Диск 1 — самый маленький. Играйте их по порядку, и головоломка решится сама; думать, какой диск можно двигать, не нужно — все ходы в списке уже допустимы.
Почему список ходов кончается на 12 дисках?
Решение для 12 дисков — это 4 095 ходов. Для 20 дисков вышло бы 1 048 575 строк, которые ни один браузер не покажет с пользой, поэтому выше 12 дисков страница даёт точное число ходов и формулу вместо списка, а анимированное поле по-прежнему проигрывает решение.