В приложении Sort Puzzle задачу, где выбор ходов, кажущихся лучшими прямо сейчас, ведёт в тупик, называют «задачей с ловушкой». Чем больше звёзд, тем чаще встречаются такие ловушки.
Сколько ловушек в задачах?
При создании задачи приложение пробует механически выбирать самые на вид удачные ходы (по числу стыков цветов в пробирках и подобным признакам) и смотрит, решится ли доска. Если не решается, это задача с ловушкой, если решается, без. Мы создали по 300 задач так же, как приложение, и посчитали.
| Сложность | Задачи с ловушкой |
|---|---|
| ★1 и ★2 | 0 |
| ★3 | 146 (около половины) |
| ★4 | 300 (все) |
| ★5 | 258 (около 90%) |
★1 и ★2 создаются без ловушек, ★3 — с вероятностью в половину задач с ловушкой. В ★4 и ★5 приложение ищет задачи с ловушкой (в ★5, если подходящая раздача никак не находится, задача может оказаться и без ловушки).
Пример: тупик за 3 хода
На этой доске 4 цвета (салатовый, розовый, оранжевый, синий) и две пустые пробирки. Доска уменьшена для наглядности, но ловушка устроена так же, как в ★3 и выше.
В пробирке 1 сверху вниз чередуются розовый, оранжевый, розовый. Если доставать цвета отсюда, число стыков цветов уменьшается на единицу за ход, поэтому кажется, что это хорошо.
- Розовый из пробирки 1 в пустую пробирку 5.
- Оранжевый из пробирки 1 в пустую пробирку 6.
- Розовый из пробирки 1 на розовый в пробирке 5.
Теперь в пробирке 1 остался один салатовый, а в пробирке 5 собрались два розовых. Но пробирки 2, 3 и 4 заполнены, и сверху у всех синий. Пробирки, которая приняла бы синий, нет, а в пробирках 5 и 6 лежат другие цвета. Переложить некуда: тупик.
После 2-го хода доска ещё решалась (ход «вернуть розовый из пробирки 5 в пробирку 1» вёл на решаемый путь). Решающим стал 3-й ход, «розовый на розовый».
Верное решение
На этой доске в первую очередь нужно заметить, что синий лежит сверху в пробирках 2, 3 и 4. Три синих нужно собрать в пустой пробирке 5.
Когда три синих собраны, в пробирках 2, 3 и 4 освободилось по одному месту. Пробирка 6 по-прежнему пуста. Отсюда доска собирается всего за 11 ходов (это минимум по перебору всех ходов).
Показать решение за 11 ходов
Три признака ловушки
- Сначала собирайте цвет, который лежит сверху в нескольких пробирках: если сверху в ряд лежит один и тот же цвет, как синий в примере, его стоит собрать в пустой пробирке. С каждым ходом в заполненных пробирках появляется место.
- Не занимайте пустые пробирки разными цветами целиком: даже если пустых пробирок две, когда в них положены разные цвета, обе станут пробирками, которые принимают только свой цвет.
- Смотрите на верх заполненных пробирок: цвет из заполненной пробирки можно переложить только на верх другой пробирки или в пустую. Ход, после которого этому цвету некуда идти, опасен.
Остальные идеи есть в статье «Советы по сортировке воды». Если вы всё-таки зашли в тупик, «Подсказка» в приложении подскажет, сколько ходов нужно отменить.
