Восьмёрка · поле 3×3
Восемь плиток и одна пустая клетка. Самая быстрая головоломка этого типа и лучшая, чтобы освоить метод.
Нажмите или потяните плитку рядом с пустой клеткой. Стрелки тоже работают. Любая перемешанная позиция решаема.
Поле 3×3 называют восьмёркой или 8 puzzle, потому что на нём восемь пронумерованных плиток и одна пустая клетка. Это самая маленькая головоломка такого типа, которую всё ещё интересно решать, и именно её чаще всего используют в курсах по информатике для объяснения алгоритмов поиска.
Не более чем за 31 ход. Любая решаемая позиция восьмёрки собирается за 31 сдвиг или меньше, и ровно две позиции требуют все 31. Типичная перемешанная позиция решается примерно за 22 хода. Человек вручную обычно тратит от 40 до 80 ходов.
У восьмёрки 9! = 362 880 возможных расстановок, и ровно половина, 181 440, решаема. Остальные 181 440 недостижимы сдвигами, сколько бы ходов вы ни сделали.
Сначала поставьте 1, 2 и 3 в верхний ряд и больше их не трогайте. Затем поставьте 4 и 7 в левый столбец. В оставшихся четырёх клетках плитки 5, 6, 8 и пустое место: крутите их по этому квадрату 2×2, пока не встанут. Если не встают, позиция нерешаема, но с полем, перемешанным допустимыми ходами, так не бывает.