Пятнашки за наименьшее число ходов
В коробке 4 × 4 лежат пятнадцать плиток с числами от 1 до 15, одна клетка пустая. За ход можно сдвинуть в пустую клетку любую соседнюю с ней плитку — сверху, снизу, слева или справа. Собранная коробка выглядит так: в первой строке 1 2 3 4, во второй 5 6 7 8, в третьей 9 10 11 12, в последней 13 14 15 и пустая клетка в правом нижнем углу.
Головоломку придумал в 1870-х годах почтмейстер Нойес Чапмен, а в 1880 году ею увлекались повсюду. Позже Сэм Лойд выдавал себя за её изобретателя и рассказывал, что обещал большую премию тому, кто соберёт коробку, где переставлены только 14 и 15. Премию так никто и не получил: ещё в 1879 году Уильям Джонсон и Уильям Стори доказали, что ровно половину расстановок собрать нельзя. Эта позиция — второй пример.
Найдите наименьшее число ходов, которое собирает коробку, или скажите, что собрать её нельзя.
Вход
Четыре строки по четыре числа — коробка по строкам сверху вниз; пустая клетка обозначена нулём. Каждое число от 0 до 15 встречается ровно один раз. Если коробку можно собрать, то не больше чем за 50 ходов.
Выход
Наименьшее число ходов или -1, если собрать нельзя.
Примеры
Пример 1
1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12
2
Пример 2
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 0
-1
Ограничения
- Время · Python
- 10000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Позиций у пятнашек 16! ≈ 2 · 1013, и поиск в ширину, который в статье о нём обходит все позиции восьмёрки, здесь не пройдёт даже на глубину 30. Какая подсказка честно оценивает, сколько ходов ещё осталось?
2Подсказка 2
За один ход двигается одна плитка и ровно на одну клетку. Сложите для всех плиток расстояние от их клеток до своих мест по горизонтали и вертикали.
3Подсказка 3
Прежде чем искать, проверьте, можно ли собрать коробку вообще. Иначе поиск будет перебирать половину из двадцати триллионов позиций.
4Идея
Это A* в пространстве позиций. Вершины — расстановки, рёбра — ходы, длина каждого хода 1. Подсказка — сумма манхэттенских расстояний плиток до их мест. Она никогда не завышает: каждый ход приближает к месту не больше одной плитки и не больше чем на одну клетку. Она и согласованная: за ход сумма меняется ровно на единицу, так что неравенство h(u) ≤ 1 + h(v) выполнено для каждого хода. Значит, первая собранная коробка, которую A* достанет из кучи, собрана за наименьшее число ходов.
Нерешаемые позиции отсекаются до поиска. В строке без пустой клетки посчитаем инверсии — пары плиток, где большая стоит раньше меньшей. Ход по горизонтали не меняет ни число инверсий, ни строку пустой клетки. Ход по вертикали переносит одну плитку через три другие: число инверсий меняется на нечётное число, и строка пустой клетки — на единицу. Поэтому чётность суммы «инверсии плюс номер строки пустой клетки» не меняется никогда. У собранной коробки она нечётна (0 + 3), значит, позиции с чётной суммой собрать нельзя. Что все остальные собрать можно, доказали Джонсон и Стори.
5Разбор
Позиция — кортеж из 16 чисел (в Go — массив, его можно класть в словарь ключом). Словарь хранит лучшее известное число ходов до каждой позиции, куча — тройки (g + h, g, позиция). Подсказку не пересчитываем заново: при ходе меняется расстояние только одной плитки, и новое h получается из старого за O(1).
Почему не жадный поиск, который всегда берёт позицию с наименьшей подсказкой? Он находит решение быстро, но длинное: на четвёртом тесте 191 ход вместо 25, на седьмом — 212 вместо 34. Без пройденного пути g в ключе кучи поиск забывает, во что ему обошлась дорога до позиции, и гарантии нет никакой. Ровно это предложение — складывать подсказку с пройденным — в 1968 году отличило A* от предшественников.
Самая трудная позиция тестов собирается за 46 ходов. A* с манхэттенской подсказкой достаёт для неё из кучи 262 251 позицию и помнит 492 093 — на позиции в 25 ходов хватает 1041. Для позиций в 60–80 ходов памяти уже не хватит. Тогда помогают две вещи. Подсказка сильнее: например, «линейные конфликты» — две плитки в своей строке, стоящие в обратном порядке, — прибавляют к манхэттенскому расстоянию по 2 хода, и подсказка остаётся честной. И поиск без хранения позиций: IDA* Ричарда Корфа (1985) делает поиск в глубину с порогом на g + h и поднимает порог, пока не найдёт решение. Корф писал, что это единственный известный алгоритм, который находит оптимальные решения случайных пятнашек в разумных пределах ресурсов.
5+Решение
6Сложность
В худшем случае A* — тот же обход пространства позиций: время и память пропорциональны числу позиций, которые он достал из кучи, умноженному на log этого числа. Подсказка не меняет порядок роста, она меняет основание: позиций с g + h не больше ответа во много раз меньше, чем позиций на расстоянии ответа. Проверка решаемости — O(1): 15 плиток, 105 пар.
7Типичные ошибки
- В ключе кучи только подсказка. Жадный поиск, ответы в разы больше настоящих.
- Нет проверки чётности. На нерешаемой позиции поиск будет обходить 1013 позиций и не уложится ни во время, ни в память.
- Подсказка с учётом пустой клетки. Если прибавлять и расстояние пустой клетки до её места, подсказка завышает: за один ход сдвигаются и плитка, и пустая клетка. В позиции за ход до сборки такая подсказка говорит 2, и A* перестаёт гарантировать кратчайший ответ.
- Позиции в списках. Список нельзя положить в словарь или множество Python ключом — нужен кортеж.