Задачи приложения Sort Puzzle не заготовлены заранее, а создаются на месте при каждой игре. И всё же каждая задача выдаётся только после проверки, что она решается. Здесь мы расскажем, как это делается.
Порядок создания
- Выбрать цвета: из 10 цветов выбирается столько, сколько нужно для сложности (для ★1 это 4 цвета).
- Перемешать и раздать: выбранные цвета собираются по 4 штуки, перемешиваются и раскладываются по 4 в пробирки с цветами. Пустые пробирки ставятся справа.
- Отбросить почти собранные пробирки: если в какой-то пробирке подряд лежат три или больше одного цвета, эта раздача не используется. Пробирка, которая с самого начала почти собрана, неинтересна.
- Проверить, решается ли: решатель на компьютере ищет последовательность ходов до победы. Если не находит, раздача не используется.
- Проверить условие ловушки: в ★3 и выше проверяется, есть ли «ловушка», когда выбор ходов, кажущихся лучшими прямо сейчас, ведёт в тупик, и раздача повторяется, пока не подойдёт под условие сложности (задачи с ловушками).
При создании каждой задачи приложение повторяет этот порядок, пока не найдёт подходящую раздачу. Даже для ★5 на создание одной задачи уходит самое большее несколько десятков миллисекунд.
Какая доля случайных досок решается?
Сколько раздач отбрасывается на шаге 4? Мы раздавали так же, как приложение, и для «честных раздач» (без пробирок с тремя и более одинаковыми цветами подряд) проверили, решаются ли они, во всех случаях.
| Сложность | Честных раздач | Решилось |
|---|---|---|
| ★1 (4 цвета, 2 пустые) | 416 | 416 |
| ★2 (6 цветов, 2 пустые) | 431 | 431 |
| ★3 (8 цветов, 2 пустые) | 453 | 453 |
| ★4 (10 цветов, 2 пустые) | 460 | 460 |
| ★5 (9 цветов, 1 пустая) | 4539 | 29 |
В ★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) каждый раз получается одна и та же последовательность. Из одного зерна получается одна и та же задача. Доска из статьи «Играть на сайте» тоже создаёт задачи по тому же порядку, что и приложение.
О том, как устроен решатель, проверяющий решаемость, рассказано в статье «Решение на компьютере».
