Запись #394458

В данной статье рассматривается решение задачи №118801 ( https://en.grandgames.net/sokoban/id118801) игры Сокобан, найденное пользователем @ovawiss.
Рассмотрим начальное положение ящиков:

Очевидно, в первую очередь надо идти вправо, сдвигая ящик «1», потому что в противном случае ящик «3» «прилипнет» к стенке. Этот ящик можно сдвинуть на одну или две клетки, принципиальной разницы нет, потом можно будет его подвинуть при необходимости. Теперь посмотрим какие из ящиков группы «2» можно двигать и куда:
1) Средний ящик вниз: будет заблокирована группа «4», её можно разблокировать сдвигом влево левого или правого ящиков группы «2», но будет заблокирован ящик «3» (с соседом снизу). Этот вариант тупиковый.
2) Левый ящик вниз и вправо до упора (если не до упора, то группа «4» будет заблокирована). Получим следующую позицию:

Ящик «1» можно сдвинуть только на одну клетку вверх (если двигать вниз, то будет заблокирована группа «2»), но оттуда его не получится сдвинуть влево, только вниз (в область справа от ящика пройти не получится). Перемещение других ящиков тоже не поможет, вариант тупиковый.
3) Правый и левый ящики вниз, потом средний вправо (средний вправо — тоже тупик, а других вариантов не осталось) Получим следующую позицию:

Теперь перемещаем ящик «1» на место «2», сдвиг любого другого ящика не имеет смысла. После этого опять остаётся только один ход: перемещение ящика «3» на место ящика «1». Получаем следующую позицию:

Дальше я сдвигал ящик «1» влево, но решение при этом получилось более сложное (если вообще получилось, точно не помню), потому двигать его не будем, а перетащим ящики «2» и «3» на места «4» и «5» соответственно (другие ходы еще больше запутывают):

В получившейся позиции имеет смысл только сдвиг ящиков «1» и «3» (с последующим перемещением ящика «2»). Если ящик «1» не сдвигать, ошибки не будет, просто перестановки вновь приведут к этой позиции. Поэтому сдвинем ящик «1» вверх на одну клетку, ящик «3» влево (тоже на одну клетку), освободив ящик «2», который переставим на место «4», а потом сдвинем ящик «5» влево до упора и вернём ящик «3» на место. Получим следующую позицию:

Теперь самые очевидные ходы такие: сдвиг ящика «1» вниз до упора, ящика «2» вниз на одну клетку и ящика «3» вправо на одну клетку. Затем сдвигаем ящик «4» на одну клетку вправо, чтобы потом не появилась заблокированная область. Получится следующая позиция:

Следующие ходы тоже вполне очевидны: сдвигаем ящик «1» на место «5», чтобы можно было переместить ящик «2» на место «6». А на место ящика «2» ставим ящик «3», место которого в свою очередь занимаем ящиком «4». После чего получаем следующую позицию:

Чтобы можно было притащить ящик «6» к остальным, нужно передвинуть ящик «1» на место «5». Для этого сдвинем ящик «3» сразу на три клетки влево (освобождая путь), сдвинем ящик «2» на одну клетку влево и переместим ящик «1». Затем вернём на место ящик «2», ящик «4» подвинём вправо (к выступу), а на его место поставим ящик «3» Получим следующую позицию:

Теперь ставим ящик «1» на место «3», затем ящик «2» тащим на место «4», а ящик «1» перемещаем на место ящика «2». Теперь осталось растолкать ящики по местам:

Теперь надо освободить ящик «1», для этого сдвинем ящики «2» и «3» влево на один и три клетки (место «5») соответственно. Затем отодвинув ящик «4» влево на одну клетку, поставим ящик «1» на место ящика «3»: (28.png)

Теперь осталось сдвинуть ящики на одну клетку в направлении стрелки, цифры обозначают относительный порядок установки: блоки «2» ставятся после блока «1», а блок «9» лучше устанавливать последним.