Приложение Sort Puzzle каждый раз раздаёт новую доску. Сколько же всего существует стартовых досок? Давайте посчитаем.
★1: 63 063 000 способов
★1 — это 16 шариков (4 цвета по 4) в 4 пробирках по 4 места.
Если представить, что 16 шариков выкладывают по порядку, снизу вверх, пробирку за пробиркой слева направо, то число способов равно числу перестановок 16 шариков, поделённому на число перестановок одинаковых цветов между собой.
16! ÷ (4! × 4! × 4! × 4!) = 20 922 789 888 000 ÷ 331 776 = 63 063 000 способов
(16! — это 16×15×…×1, а 4! — это 4×3×2×1=24.)
Кроме того, приложение выбирает 4 цвета из 10, то есть цвета можно выбрать 210 способами. Если различать и цвета, получится 63 063 000 × 210 = 13 243 230 000 способов (около 13,2 млрд).
Числа по сложности
Если не учитывать выбор цветов и сравнить только способы расстановки, то с ростом числа цветов они резко растут.
| Сложность | Способов расстановки | Доля честных раскладок |
|---|---|---|
| ★1 (4 цвета) | около 63,06 млн | 80,42% |
| ★2 (6 цветов) | около 3,2×10¹⁸ | 87,07% |
| ★3 (8 цветов) | около 2,4×10²⁴ | 90,36% |
| ★4 (10 цветов) | около 1,3×10³⁴ | 92,33% |
| ★5 (9 цветов) | около 1,4×10³² | 91,46% |
10¹⁸ — это единица с 18 нулями (квинтиллион). Число для ★4 — это примерно 1,3 от единицы с 34 нулями.
Честных раскладок около 80–90%
Приложение не использует раскладки, в которых есть пробирка с тремя и более одинаковыми цветами подряд (пробирка, которая с самого начала почти собрана, неинтересна). «Доля честных раскладок» в таблице — это доля раскладок без таких пробирок. Мы подсчитали её точно, последовательно считая число цветов в пробирках.
Для ★1 из 63 063 000 способов 50 717 088 способов (80,42%) — честные раскладки. Чем больше цветов, тем ниже вероятность подряд идущих одинаковых цветов, поэтому доля честных раскладок растёт.
Все доски размера ★1 решаются
Мы перебором проверили, решаются ли все честные раскладки ★1. Если считать одинаковыми раскладки, которые отличаются лишь порядком пробирок или перекраской цветов, их будет 89 675 видов.
Мы добавили к этим 89 675 видам две пустые пробирки и перебрали все ходы для каждой: решились все. Даже 111 383 вида, включая нечестные раскладки (с тремя и более одинаковыми цветами подряд в пробирке), тоже решились все.
Значит, при 4 цветах и двух пустых пробирках любая раскладка обязательно решается. Приложение не отбрасывает «нерешаемые раскладки» в ★1.
Для ★2–★4 с большим числом цветов проверить всё невозможно, но в проверенных диапазонах по 400–500 раскладок решились все. А вот в ★5 с одной пустой пробиркой не решается большинство раскладок (как создаются всегда решаемые задачи).
