Почти собрано. Почему эта головоломка не решается?
Две фишки стоят неправильно — кажется, осталась мелочь. Но беспорядочная доска собирается, а почти готовая не сдастся никогда. Попробуйте обе и найдите невидимую границу.
Какая доска сдастся первой?
На доске А всё выглядит обнадёживающе: верхние два ряда уже собраны, внизу только семёрка с восьмёркой поменялись местами. На доске Б числа разбросаны, пустая клетка зияет посередине. Если бы за решение давали приз, с какой вы начали бы?
У Б есть путь к победе. У А нет ни короткого пути, ни длинного. Это не соревнование на терпение: попробуйте несколько ходов, затем раскройте подсказку под полем. Счётчик покажет, что именно не меняется, пока фишки путешествуют.
Перед вами маленькая родственница пятнашек: восемь фишек на поле 3 × 3. Двигать можно только соседнюю с пустой клеткой фишку, по горизонтали или вертикали. Цель всегда одна: 1 2 3 в первом ряду, 4 5 6 во втором, 7 8 и пустая клетка в третьем. Менять цель по дороге нельзя.
Собрать или доказать невозможность
Одна из этих двух досок не решается. Нескольких пробных ходов достаточно: под полем можно раскрыть причину. Без JavaScript ниже доступны обе расстановки, правила и решение доски Б.
Нажимайте на жёлтую фишку рядом с пустой клеткой. С клавиатуры — Tab и Enter или пробел. Цель: строки 1 2 3 / 4 5 6 / 7 8 ·.
Почему одна доска не сдаётся?
Прочитайте числа по строкам, пропуская пустую клетку:
Инверсия — пара, в которой большее число стоит раньше меньшего. На этой доске 3 × 3 любой разрешённый ход сохраняет чётность числа инверсий. У цели их ноль.
Две доски, одна цель
Можно вырезать восемь бумажных фишек и передвигать их на сетке 3 × 3. Разрешён только сдвиг соседней фишки в пустую клетку по горизонтали или вертикали. Поднимать и менять фишки местами нельзя.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | · |
А · почти собрано
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 8 | 7 | · |
Порядок без пустого места: 1 2 3 4 5 6 8 7. Одна инверсия: 8 перед 7. Решения нет: нечётное число не станет чётным от разрешённых ходов.
Б · беспорядок
| 5 | 4 | 2 |
| 7 | · | 3 |
| 8 | 1 | 6 |
Порядок без пустого места: 5 4 2 7 3 8 1 6. Инверсий 14 — чётное число. Эта доска решается.
Один маршрут: передвигайте в пустую клетку фишки 1 → 8 → 7 → 5 → 4 → 1 → 5 → 4 → 1 → 2 → 3 → 6. Это 12 ходов; каждый номер обозначает фишку, а не направление.
Слишком близко, чтобы сдаться
Начните с А. Стоит опустить шестёрку или сдвинуть семёрку — и аккуратная картинка разваливается. Кажется, надо ненадолго пожертвовать готовым рядом, обвести две непослушные фишки вокруг остальных и вернуть всё обратно.
Жертвовать готовыми рядами действительно иногда приходится. Но для А не поможет даже это. Ограничение относится ко всему полю: любая разрешённая последовательность ходов останется по другую сторону невидимой границы от цели. Давайте найдём эту границу, не перебирая все маршруты.
Вместо квадратной доски прочитайте одну строку: слева направо в верхнем ряду, потом в среднем, потом в нижнем. Пустое место просто пропускайте. У А получится 1 2 3 4 5 6 8 7. Теперь видно ровно одно нарушение порядка: восьмёрка встретилась раньше семёрки.
Считать нужно пары, а не неправильные места
Такую пару называют инверсией: большее число стоит в строке раньше меньшего. Числа не обязаны быть соседями. Например, в порядке 3 1 2 есть две инверсии: 3 перед 1 и 3 перед 2. А пара 1 и 2 стоит правильно.
Это другой счёт, чем «сколько фишек не на месте». На А неправильных мест два, а инверсия всего одна. На Б инверсий четырнадцать. Первое впечатление верно в одном: беспорядка у Б больше. Ошибка возникает, когда мы принимаем малый беспорядок за гарантию близкого решения.
В собранной доске строка выглядит как 1 2 3 4 5 6 7 8. Ни одно большее число не обгоняет меньшее. Инверсий ноль — чётное число. У А одна — нечётное. Пока это лишь два разных числа. Почему нельзя постепенно превратить одно в другое?
Ход, который ничего не меняет
Сдвиньте фишку в пустое место по горизонтали. На самой доске она передвинулась, но в строке без пустой клетки осталась между теми же числами. Она никого не обогнала. Список чисел и число инверсий не изменились.
Вертикальный ход интереснее. При чтении по строкам фишка перескакивает через два числа. В её отношениях с каждым из них происходит переворот: было «раньше», стало «позже», или наоборот. Поэтому инверсий может стать на две больше, на две меньше или столько же. Из чётного числа выходит чётное; из нечётного — нечётное.
Попробуйте это на А: опустите шестёрку в пустой правый нижний угол. Строка станет 1 2 3 4 5 8 7 6. Теперь неправильных пар три: 8 перед 7, 8 перед 6, 7 перед 6. Беспорядок вырос с одного до трёх, а нечётность сохранилась. Отмените ход — снова одна.
Вот и граница. Каждый разрешённый ход сохраняет чётность. Любая цепочка таких ходов тоже её сохраняет. Можно получить одну, три, пять инверсий; получить ноль из нечётного числа нельзя. Для этой доски «попробовать ещё» не приблизит развязку.
Почему Б всё-таки собирается
Четырнадцать инверсий — чётное число. Для стандартного поля 3 × 3 это не только необходимое условие: любая расстановка с чётным числом инверсий достижима из нашей цели разрешёнными ходами. Этот критерий сформулирован в материалах Принстона внизу страницы.
Но разрешимость не подсказывает, какую фишку двигать следующей. Попробуйте собрать Б сами; если застрянете, откройте «Исходные доски и решение Б». Там есть маршрут из двенадцати ходов. Номер означает фишку, которую надо сдвинуть в пустую клетку. Можно отменять шаги и начинать заново.
На пути число инверсий иногда растёт. Это нормально: счётчик различает две семьи позиций, а не измеряет расстояние до победы. У задачи может быть решение, которое сначала выглядит как ухудшение.
Как случайно испортить хорошую головоломку
Если перемешивать собранную доску только разрешёнными ходами, решение останется всегда. Достаточно пройти те же ходы в обратном порядке — пусть вы и не запомнили их. Но если вынуть две числовые фишки и обменять местами, можно перейти через границу, которую обычные ходы не пересекают.
Из всех возможных расстановок восьми разных фишек и пустого места до этой цели доходит ровно половина. Поэтому «я просто рассыпал детали и собрал рамку как попало» — совсем другой способ перемешивания.
Сделайте бумажную версию: сетка 3 × 3 и восемь маленьких квадратиков. Соберите цель, затем тайком поменяйте 7 и 8. Предложите другому человеку не потратить на неё вечер, а объяснить невозможность. Победа теперь состоит не в последнем удачном движении, а в доказательстве, что такого движения не будет.
И не переносите наш счётчик без поправки на обычные пятнашки 4 × 4: там вертикальный ход проходит мимо трёх чисел, поэтому нужно учитывать ещё положение пустой клетки. У этой маленькой доски свой секрет — он уже не секрет для вас.