Если вы тратили тридцать минут на 15-головоломку, которая просто не дочиняется — каждый ход в итоге приводит к двум переставленным плиткам в конце, — есть шанс, что пазл математически нерешаем. Ровно половина всех конфигураций 15-puzzle такова. Плохо написанное приложение может случайно сгенерировать одну.
Эта статья — практическая проверка. Полное математическое обоснование — в теореме чётности; эта остаётся простой.
Проверка за 30 секунд
Посмотрите на плитки в порядке чтения — слева направо по строкам, сверху вниз — игнорируя пустую.
Для каждой пары плиток сосчитайте, сколько раз большее число стоит раньше меньшего. Это число — число инверсий.
Затем заметьте, в какой строке пустая клетка, считая снизу (нижняя строка — 1, выше — 2, потом 3, потом 4 наверху).
Сложите число инверсий и строку пустой снизу. Если результат нечётен — пазл решаем. Если чётен — нет.
Это всё. Это вся проверка.
Разобранный пример
Допустим, доска такая:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Порядок чтения: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Считаем инверсии. Нужно найти каждую пару, где большее идёт раньше меньшего. Проходим: 15 стоит раньше 14, и это единственная инверсия. Значит, число инверсий = 1.
Пустая в нижней строке → строка 1 снизу.
Сумма: 1 + 1 = 2. Чётно. Эта доска нерешаема.
Это, кстати, призовая головоломка Сэма Лойда 1880 года. Он предложил $1000 тому, кто её решит. Пазл был нерешаемым; деньги остались при нём.
Другой пример
Доска:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Порядок чтения: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Считаем инверсии:
- 5 раньше 1 → 1 инверсия (5 > 1, и 5 идёт первой)
- 5 раньше 3 → 1 инверсия
- 5 раньше 4 → 1 инверсия
- 5 раньше 2 → 1 инверсия
- 3 раньше 2 → 1 инверсия
- 4 раньше 2 → 1 инверсия
Итого инверсий: 6.
Пустая в нижней строке → строка 1.
Сумма: 6 + 1 = 7. Нечётно. Решаема.
Почему это работает (кратко)
Допустимый сдвиг либо двигает плитку горизонтально (не меняет инверсий, не меняет строку пустой), либо вертикально (меняет инверсии на нечётное число, меняет строку пустой на 1).
В любом случае сумма инверсий + строка пустой остаётся чётной или нечётной так же, как стартовала. Эта сумма — инвариант, свойство пазла, которое допустимые ходы не меняют.
Целевое состояние (1‑2‑3‑...‑15 с пустой в правом нижнем) имеет 0 инверсий и пустую в строке 1 снизу — сумма 1, нечётно. Так что у любой решаемой доски сумма нечётна. У любой с чётной — недостижима из цели.
Полное доказательство со всеми случаями — на странице теоремы чётности.
А что насчёт 8-puzzle (3×3)?
Для 3×3 проверка проще:
- Сосчитайте инверсии в порядке чтения.
- Если чётно, решаема.
- Если нечётно, нерешаема.
Не нужно отслеживать строку пустой для 3×3 — симметрия пазла делает зависимость от строки избыточной.
(Для 5×5 — то же правило, что для 3×3. Для 6×6 — то же, что для 4×4. Правило: «строка пустой имеет значение, когда N чётно».)
Что делать, если приложение генерирует нерешаемые
Этого не должно случаться. Хорошо написанное приложение использует один из двух методов, чтобы избежать этого:
Генерировать, идя назад от цели. Стартовое состояние = цель, применяйте случайные допустимые ходы, и результирующее состояние — стартовая позиция. Каждая позиция, сгенерированная так, решаема по построению.
Генерировать случайно, потом тестировать чётностью. Перемешайте плитки равномерно случайно; посчитайте проверку чётности; если чётна, поменяйте местами любые две плитки, чтобы починить. Результирующая позиция гарантированно решаема.
Если встречаете нерешаемый пазл в приложении — это приложение сломано. Сообщите баг, поменяйте приложение. Slide Puzzle использует метод обхода назад от цели и не может произвести нерешаемые стартовые позиции.
Что делать, если подозреваете свой физический пазл нерешаемым
Две вещи:
- Запустите проверку. Инверсии плюс строка пустой. Если чётно, физические кусочки собраны неправильно. Вытащите одну плитку, поменяйте местами с соседней — и пазл решаем.
- Если даже после смены пазл сопротивляется — сопротивление это ваша стратегия, не пазл.
Проверка чётности — около тридцати секунд. Сделать её перед тем, как утопить ещё час в застрявшей доске, — разумное использование этих секунд.