За какое минимальное число ходов можно решить сортировку цветов? Для размера ★1 в приложении Sort Puzzle (4 цвета, 2 пустые пробирки) можно проверить все раскладки. Мы посчитали минимальное число ходов для каждой раскладки в режиме «Переливать».
Как мы считали
- Проверяем только «честные раскладки», где нет пробирки с тремя и более одинаковыми цветами подряд (приложение выдаёт только такие).
- Раскладки, отличающиеся лишь порядком пробирок или перекраской цветов, считаем одной. Получается 89 675 видов (сколько существует раскладок).
- Для каждой раскладки раскрываем все позиции, достижимые за 1 ход, за 2 хода и так далее, и находим число ходов, при котором доска впервые собирается (поиск в ширину).
Распределение минимума ходов
| Минимум ходов | Видов раскладок |
|---|---|
| 5 | 3 |
| 6 | 8 |
| 7 | 124 |
| 8 | 741 |
| 9 | 3 523 |
| 10 | 11 070 |
| 11 | 21 321 |
| 12 | 26 778 |
| 13 | 19 271 |
| 14 | 6 635 |
| 15 | 197 |
| 16 | 4 |
Чаще всего встречается 12 ходов, а на 10–13 ходов приходится больше 80% всех раскладок. За 5 ходов решаются только 3 вида раскладок, а 16 ходов нужно всего для 4 видов.
(Числа здесь — это «виды». Вероятность, с которой они реально выпадают в приложении, у разных видов немного отличается.)
Самая короткая доска (5 ходов)
В каждой пробирке по два одинаковых цвета подряд. С помощью двух пустых пробирок доска собирается за 5 ходов.
Самая долгая доска (16 ходов)
Пробирки 1 и 2, а также 3 и 4 абсолютно одинаковы. В каждой пробирке соседние цвета все разные, а красный и салатовый лежат на дне по две пробирки.
Показать решение за 16 ходов
Как найти нижнюю границу числа ходов
Минимум ходов можно не перебирать, а найти по одному виду доски его нижнюю границу (число, меньше которого быть не может).
- Посчитайте число стыков цветов внутри пробирок.
- Если один цвет лежит на дне нескольких пробирок, прибавьте «их число минус 1».
Эта сумма за одно переливание уменьшается не больше чем на 1, поэтому не превышает минимума ходов (решение на компьютере).
- Доска на 5 ходов: стыков 4, красный лежит на дне двух пробирок, прибавляем 1, нижняя граница 5. Это ровно минимум.
- Доска на 16 ходов: стыков 12, красный и салатовый лежат на дне двух пробирок, прибавляем 2, нижняя граница 14. На самом деле нужно 16 ходов.
Из 89 675 видов нижняя граница в точности совпала с минимумом у 38 571 вида (около 43%). В остальных случаях нужно больше, чем нижняя граница.
А на досках побольше
Когда цветов больше, раскладок слишком много, чтобы проверить все. Среднее минимальное число ходов по 20 задачам, созданным тем же способом, что и в приложении, составило 11,8 для ★1 и 18,1 для ★2 (6 цветов). Для ★3 и выше даже минимум для одной задачи считается долго.
«Подсказка» в приложении показывает не минимальное решение, а то, которое находится быстро. Если хотите попробовать решить за минимум, ориентируйтесь на нижнюю границу и продумывайте последовательность сами (как работает подсказка).
