За какое минимальное число ходов можно решить сортировку цветов? Для размера ★1 в приложении Sort Puzzle (4 цвета, 2 пустые пробирки) можно проверить все раскладки. Мы посчитали минимальное число ходов для каждой раскладки в режиме «Переливать».

Как мы считали

  • Проверяем только «честные раскладки», где нет пробирки с тремя и более одинаковыми цветами подряд (приложение выдаёт только такие).
  • Раскладки, отличающиеся лишь порядком пробирок или перекраской цветов, считаем одной. Получается 89 675 видов (сколько существует раскладок).
  • Для каждой раскладки раскрываем все позиции, достижимые за 1 ход, за 2 хода и так далее, и находим число ходов, при котором доска впервые собирается (поиск в ширину).

Распределение минимума ходов

Минимум ходовВидов раскладок
53
68
7124
8741
93 523
1011 070
1121 321
1226 778
1319 271
146 635
15197
164

Чаще всего встречается 12 ходов, а на 10–13 ходов приходится больше 80% всех раскладок. За 5 ходов решаются только 3 вида раскладок, а 16 ходов нужно всего для 4 видов.

(Числа здесь — это «виды». Вероятность, с которой они реально выпадают в приложении, у разных видов немного отличается.)

Самая короткая доска (5 ходов)

123456
Ход 1: 3→5 (2)
123456
Ход 2: 1→3 (2)
123456
Ход 3: 4→5 (2)
123456
Ход 4: 2→4 (2)
123456
Ход 5: 1→2 (2)
123456
Собрано

В каждой пробирке по два одинаковых цвета подряд. С помощью двух пустых пробирок доска собирается за 5 ходов.

Самая долгая доска (16 ходов)

123456

Пробирки 1 и 2, а также 3 и 4 абсолютно одинаковы. В каждой пробирке соседние цвета все разные, а красный и салатовый лежат на дне по две пробирки.

Показать решение за 16 ходов
123456
Ход 1: 1→5
123456
Ход 2: 1→6
123456
Ход 3: 2→5
123456
Ход 4: 2→6
123456
Ход 5: 1→2
123456
Ход 6: 1→5
123456
Ход 7: 2→1 (2)
123456
Ход 8: 2→5
123456
Ход 9: 3→2
123456
Ход 10: 3→6
123456
Ход 11: 3→1
123456
Ход 12: 2→3
123456
Ход 13: 4→3
123456
Ход 14: 4→6
123456
Ход 15: 4→1
123456
Ход 16: 3→4 (3)
123456
Собрано

Как найти нижнюю границу числа ходов

Минимум ходов можно не перебирать, а найти по одному виду доски его нижнюю границу (число, меньше которого быть не может).

  1. Посчитайте число стыков цветов внутри пробирок.
  2. Если один цвет лежит на дне нескольких пробирок, прибавьте «их число минус 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 и выше даже минимум для одной задачи считается долго.

«Подсказка» в приложении показывает не минимальное решение, а то, которое находится быстро. Если хотите попробовать решить за минимум, ориентируйтесь на нижнюю границу и продумывайте последовательность сами (как работает подсказка).