Есть один метод для решения слайд-пазлов вручную. Он не зависит от размера доски. Освоив его на 3×3, вы получаете его и для 4×4, 5×5, 6×6, и любого большего размера. Вот этот метод.
План
Для N×N пазла:
- Соберите строку 1 — поставьте плитки 1, 2, …, N в верхнюю строку.
- Соберите столбец 1 — поставьте плитки N+1, 2N+1, … в первый столбец под строкой 1.
- Теперь у вас пазл (N−1)×(N−1). Рекурсия.
- Базовый случай — когда доходите до 2×2, оставшиеся плитки либо на местах, либо нужна проверка чётности.
Это весь алгоритм. Три предложения. Остальное — механика.
Механика: углы
Поставить первые плитки строки или столбца легко. Сложность — поставить последнюю плитку, угловую.
Для правого верхнего угла строки 1 (плитка N на N×N пазле):
- Не пытайтесь сдвинуть плитку N напрямую в угол. Она там не останется.
- Сначала поставьте предыдущую плитку (N−1) в угол.
- Поставьте плитку N прямо под N−1.
- Теперь проверните пару: подведите пустую в угол (выталкивая N−1), сдвиньте N−1 вниз-и-влево, сдвиньте N вверх в угол, сдвиньте N−1 вправо.
Эффект: N−1 и N оказываются правильно поставленными, не потревожив ничего слева.
Это Г-образный угловой манёвр. Тот же приём, зеркально, работает в нижнем левом углу столбца 1.
Если запомните только один кусок техники — запомните этот. Всё остальное выводится из него.
Механика: середины
Для внутренней части строки (плитки 1 через N−2 в верхней строке) размещение прямое:
- Найдите плитку.
- Подведите её на позицию, соседнюю с её назначением.
- Используйте пустую клетку, чтобы задвинуть на место.
Возможно, придётся подвинуть в сторону другие непоставленные плитки. Это нормально — они непоставленные. Пока вы не трогаете уже поставленные плитки слева, строка наращивается чисто.
Правило, которое держит вас в безопасности: никогда не пускайте пустую клетку через уже поставленную плитку. Если пустой нужно пройти от правой стороны доски к левой стороне поставленной плитки, придётся обойти её через непоставленные клетки.
Почему «строка, потом столбец»
Две причины:
- Зеркальная симметрия. Угловой манёвр для строки и для столбца — это один и тот же приём, зеркально. Освоив один, вы учите и второй.
- У пустой есть пространство для работы. После решения строки 1 у пустой есть нижние (N−1) строк для манёвра. После столбца 1 — (N−1)×(N−1) область. Рабочая зона сужается изящно.
Можно было бы чередовать (строка 1, столбец 1, строка 2, столбец 2, ...), но естественный ритм — делать парами по периметру и рекурсивно.
Рекурсия
Когда строка 1 и столбец 1 готовы, оставшийся (N−1)×(N−1) пазл содержит плитки, которые должны попасть в другую целевую конфигурацию — ту же численную последовательность, но в других позициях. Хорошая новость: методу всё равно. Решите новую верхнюю строку, новый левый столбец, рекурсивно. В итоге достигнете базового случая 2×2 или 3×3.
Для базового случая 3×3 последние три плитки можно прокрутить на места повторными одиночными ходами. Для базового случая 2×2 (который может возникнуть в самом конце больших пазлов) — то же самое.
Почему это работает на любом размере
У семейства слайд-пазлов есть полезное рекурсивное свойство: решение строки-и-столбца сводит пазл к меньшему пазлу того же рода. Математика прямолинейна. После размещения N плиток в строке 1 (и без последующих касаний) оставшаяся игра живёт на сетке шириной (N−1), у которой не хватает одной строки. После размещения левого столбца — на (N−1)×(N−1).
Это сведение применимо на каждом шаге. 6×6 сводится к 5×5, который к 4×4, который к эндшпилю 3×3. Эндшпиль 3×3 — единственный со специальной техникой; всё остальное сводится к нему.
Эта рекурсивная структура — причина, по которой слайд-пазлы часто используют в курсах программирования для обучения «разделяй и властвуй». Доказательство корректности — один абзац; реализация — тело алгоритма.
Как быстро вы становитесь
Новый солвер, применяющий метод буквально:
За несколько партий на размер эти времена сокращаются вдвое. Метод тот же; это просто моторная память углового манёвра.
Для чего этот метод не подходит
Оптимальные решения. Компьютер с реальным солвером найдёт последовательности на 30–50% короче, чем даёт метод строки-и-столбца. Человек не запустит эти алгоритмы в голове.
Соревнования по скорости. Топовые человеческие спид-солверы используют метод строки-и-столбца как базу, но агрессивно срезают углы, делая частичные размещения, которые потом «откатывают». Это быстрее, но сложнее учить.
Для всех остальных метод строки-и-столбца — это и есть метод.