В 1880 году американский составитель головоломок Сэм Лойд объявил приз $1000 тому, кто решит конкретную 15-головоломку: стандартное расположение 1‑через‑15 с поменянными местами 14 и 15. Помешательство на пазлах уже шло по Америке; приёмчик Лойда добавил ракетного топлива. Тысячи пытались. Никто не выиграл.
Никто не выиграл по причине. Доска Лойда была доказуемо нерешаема, и доказательство достаточно элементарно, чтобы поместиться на одной странице. Эта статья — та страница.
Утверждение
Ровно половина из всех 16!/2 ≈ 10 461 394 944 000 способов расположить пятнадцать плиток и пустую на доске 4×4 решается в стандартную цель. Другая половина не решается. «14 и 15 переставлены» Лойда — в нерешаемой половине.
Это обобщается. На каждом N×N слайд-пазле половина всех конфигураций нерешаема. У 3×3 8-puzzle 9!/2 = 181 440 решаемых из 362 880 всех; у 24, 35 и так далее — то же правило.
Инверсии
Доказательству нужно одно определение. Прочитайте плитки в порядке чтения — слева направо по строкам, ряд за рядом — игнорируя пустую. Получите последовательность из пятнадцати чисел.
Инверсия — это пара (a, b), где a встречается в последовательности раньше b, но a > b. Сосчитайте каждую такую пару по всей последовательности. Это и есть число инверсий доски.
Пример: целевое состояние 1,2,3,…,15 имеет ноль инверсий. «14 и 15 переставлены» Лойда даёт последовательность 1,2,3,…,13,15,14, у которой ровно одна инверсия (пара 15,14).
Ключевая лемма: сдвиг меняет чётность контролируемо
Что происходит с числом инверсий при допустимом ходе?
-
Горизонтальные сдвиги (плитка едет влево или вправо на одну клетку): сдвигаемая плитка меняет позицию в последовательности порядка чтения ровно на один слот. Её относительный порядок с каждой другой плиткой в последовательности остаётся в точности тем же — потому что горизонтальное движение не меняет строку плитки и не меняет, какие плитки её предшествуют или следуют в порядке строки. Число инверсий не меняется.
-
Вертикальные сдвиги (плитка едет вверх или вниз на одну клетку): сдвигаемая плитка перепрыгивает через три другие плитки в последовательности порядка чтения — три плитки в строке, через которую проходит. Каждая из этих трёх либо переходит из «после» в «до», либо наоборот, что означает, что каждая вносит +1 или -1 в число инверсий. Сумма трёх ±1 всегда нечётна. Число инверсий меняется на нечётное.
Итог: горизонтальный сдвиг сохраняет чётность числа инверсий (чётное/нечётное). Вертикальный — переворачивает её.
Строка пустой тоже переворачивается на вертикальных сдвигах
Отследите строку пустой, считая строки сверху. Горизонтальный сдвиг оставляет пустую в той же строке. Вертикальный двигает её на одну строку, так что чётность строки пустой меняется (чётная ↔ нечётная).
Теперь у нас две вещи, меняющиеся вместе:
- Чётность инверсий переворачивается ⇔ вертикальный сдвиг.
- Чётность строки пустой переворачивается ⇔ вертикальный сдвиг.
Их сумма инвариантна под любым допустимым сдвигом. Мы нашли сохраняющуюся величину.
Теорема чётности
Определите инвариант:
P = (число инверсий) + (номер строки пустой, считая снизу, начиная с 1)
Это та сохраняющаяся величина. На каждом допустимом сдвиге P меняется на чётное число, так что её чётность (чётный/нечётный) никогда не меняется.
Целевое состояние имеет ноль инверсий и пустую в строке 1 снизу — поэтому P = 1 (нечётно). Любая доска с чётным P недостижима из цели, и наоборот, цель недостижима из такой доски.
Это даёт чистый тест решаемости для 15-головоломки:
- Прочитайте плитки в порядке строки, игнорируя пустую.
- Сосчитайте инверсии.
- Сосчитайте строку пустой снизу (1, 2, 3 или 4).
- Сложите. Если сумма нечётна — доска решаема. Если чётна — нет.
«14 и 15 переставлены» Лойда имеет 1 инверсию и пустую в строке 1 снизу — сумма 2, чётная, нерешаема.
Как это выглядит для других размеров
Правило чётности N×N зависит от того, чётно N или нечётно. Общее утверждение:
- N нечётно (3×3, 5×5, …): доска решаема тогда и только тогда, когда число инверсий чётно. Строка пустой не имеет значения, потому что её чётность определяется чётностью инверсий по соображениям симметрии.
- N чётно (4×4, 6×6, …): доска решаема тогда и только тогда, когда (число инверсий) + (строка пустой снизу) нечётно.
Для 3×3 тест — просто «чётно ли число инверсий?». Это проще 4×4-версии, и можно запомнить за минуту.
Приятное следствие
Поскольку ровно половина всех конфигураций решаема, случайное перемешивание плюс проверка чётности быстрее, чем случайное перемешивание плюс попытка решить. Приложения, которым нужно гарантировать решаемые стартовые позиции, либо:
- Предварительно проверяют чётность и перешаффливают при провале.
- Генерируют, идя назад от цели, применяя случайные допустимые сдвиги. Это гарантирует решаемость по построению, и так делают большинство приложений, наше включительно.
Если когда-нибудь играете в слайд-пазл и не можете решить — приложение сгенерировало плохо, не ваша вина, и пазл не от Вселенной.
Сноска про Сэма Лойда
Приз $1000 Лойда — одна из лучше задокументированных практических шуток в истории головоломок. Математиком, доказавшим нерешаемость — независимо — был либо Уильям Джонсон и Уильям Стори (1879, American Journal of Mathematics), либо сам Лойд, в зависимости от того, кому верить. Лойд был знаменитой саморекламирующейся фигурой, заявившей о нескольких изобретениях, которые не изобретал; саму 15-головоломку изобрёл Ноес Чепмен в 1874 году, за шесть лет до приза.
Что Лойд реально внёс — это приз, рекламу и нерешаемый вариант. Полезный вклад, если не тот, что он рекламировал.