Задачи приложения Sort Puzzle не заготовлены заранее, а создаются на месте при каждой игре. И всё же каждая задача выдаётся только после проверки, что она решается. Здесь мы расскажем, как это делается.

Порядок создания

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

При создании каждой задачи приложение повторяет этот порядок, пока не найдёт подходящую раздачу. Даже для ★5 на создание одной задачи уходит самое большее несколько десятков миллисекунд.

Какая доля случайных досок решается?

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

СложностьЧестных раздачРешилось
★1 (4 цвета, 2 пустые)416416
★2 (6 цветов, 2 пустые)431431
★3 (8 цветов, 2 пустые)453453
★4 (10 цветов, 2 пустые)460460
★5 (9 цветов, 1 пустая)453929

В ★1–★4, где пустых пробирок две, все посчитанные честные раздачи решились. А вот в ★5 с одной пустой пробиркой из 4539 раздач решились только 29 (0,64%). Остальные — раздачи, которые не собрать, как ни двигай.

С одной пустой пробиркой решаемость резко падает

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

Число цветов (1 пустая)Доля решённых
3 цвета72,7%
4 цвета44,9%
5 цветов26,3%
6 цветов14,0%
7 цветов6,0%
8 цветов2,3%
9 цветов0,64%

С каждым добавленным цветом доля решаемых раздач падает примерно вдвое, а при большом числе цветов ещё быстрее. Видимо, причина в том, что при одной пустой пробирке первый ход можно сделать только в неё, и выбор путей оттуда невелик (как решать ★5 (одна пустая пробирка)).

Как создаётся ★5

В ★5 решаемые раздачи встречаются редко, поэтому приложение пересдаёт до 400 раз. Если и после этого не нашлось, оно переключается на другой способ создания.

  • Разрушить собранную доску: начать с собранной доски и случайно разрушать её ходами в обратную сторону. Если сделать пройденные в обратную сторону ходы обратно, доска обязательно соберётся, поэтому решаемость гарантирована.

Когда мы создали 500 задач ★5 так же, как приложение, 18 из них оказались такими «разрушенными досками». У разрушенной доски в пробирках бывает не по 4 слоя.

Из одного зерна получается одна и та же задача

Случайные числа, которые используются при создании задач, устроены так, что при заданном числе-«зерне» (SplitMix64) каждый раз получается одна и та же последовательность. Из одного зерна получается одна и та же задача. Доска из статьи «Играть на сайте» тоже создаёт задачи по тому же порядку, что и приложение.

О том, как устроен решатель, проверяющий решаемость, рассказано в статье «Решение на компьютере».