Прежде чем выдать задачу, приложение Sort Puzzle проверяет на компьютере, что она решается. Следующий ход «Подсказки» — это тоже первый ход решения, которое нашёл тот же решатель. Здесь мы расскажем, как он устроен.

Позиции и ходы

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

Самый простой способ поиска — поиск в ширину: сначала раскрываем все позиции, достижимые за 1 ход, потом все достижимые за 2 хода и так далее. Он всегда находит ответ с минимальным числом ходов, но при большом числе цветов позиций приходится проверять огромное количество.

Оценка «расстояния» до победы

Поэтому приложение для каждой позиции считает оценку расстояния до победы и сначала проверяет позиции, которые кажутся ближе. Оценка — это сумма двух величин.

  1. Число стыков цветов в пробирках: сколько мест, где цвет меняется, если смотреть снизу.
  2. Совпадения на дне: если один цвет лежит на дне нескольких пробирок, то их число минус 1.
123456

Для этой доски стыков цветов в пробирке 1 два, в пробирке 2 два, в пробирке 3 три и в пробирке 4 три, всего 10. Голубой лежит на дне пробирок 3 и 4, поэтому совпадение на дне равно 1. Оценка — 11. В собранной позиции нет ни стыков, ни совпадений, поэтому оценка равна 0.

Оценка не превышает минимума ходов

У этой оценки есть хорошее свойство: за один ход она уменьшается не больше чем на 1.

  • За одно переливание число стыков в исходной пробирке уменьшается не больше чем на 1. Переливают на такой же цвет или в пустую пробирку, поэтому в целевой пробирке стыки не появляются и не исчезают.
  • Совпадение на дне уменьшается на 1 только тогда, когда пробирка опустошается, то есть когда переносится последний подряд идущий слой, и при этом стыки не уменьшаются.

Значит, доске с оценкой 11 нужно не меньше 11 ходов. Мы перебрали больше 120 тысяч ходов на разных досках и не нашли ни одного хода, который уменьшал бы оценку на 2 и больше. Минимум ходов для доски выше — ровно 11.

Взвешенный поиск A*

Приложение ставит позиции оценку «число пройденных ходов + 3 × оценка расстояния» и сначала проверяет позиции с меньшей оценкой. Это взвешенный поиск A* («А-звезда»).

  • Если взять вес 1 (обычный поиск A*), то, поскольку оценка является нижней границей минимума ходов, всегда находится ответ с минимальным числом ходов.
  • Если взять вес 3, то позиции с малой оценкой проверяются гораздо раньше, и ответ находится намного быстрее. Зато ответ может оказаться чуть длиннее минимального.

На задачах по 20 штук, созданных тем же способом, что и в приложении, мы сравнили число проверенных позиций и число ходов в найденном решении (поиск в ширину для ★3 не считали, потому что позиций слишком много).

★1 (4 цвета, 2 пустые)Проверено позицийХодов в решении
Поиск в ширину53711,8
A* (вес 1)20311,8
A* (вес 3)3911,9
★2 (6 цветов, 2 пустые)Проверено позицийХодов в решении
Поиск в ширину293418,1
A* (вес 1)62218,1
A* (вес 3)6418,8

В обоих случаях это среднее по 20 задачам. С весом 3 ответ находится при числе позиций в несколько десятков раз меньшем, чем при поиске в ширину, а число ходов растёт лишь незначительно.

Как сократить число проверяемых ходов

Решатель приложения уменьшает число проверяемых позиций и другими способами.

  • Не различать порядок пробирок: если содержимое пробирок одинаково, позиции с разным порядком считаются одной.
  • Не проверять бессмысленные ходы: исключаются ход пробирки из одного цвета в пустую (форма не меняется) и ход во вторую и следующие пустые пробирки (получается та же позиция, что и для первой).
  • Искать только ходами «Переливать»: и задачи для режима «Складывать» проверяются на то, решаются ли они ходами переливания (чем отличаются «Переливать» и «Складывать»).
  • Установить предел: если за 60 тысяч проверенных позиций решение не найдено, считается «неизвестно», и эта раздача не используется.

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