Гра

Напевно, всім відома дитяча гра «п'ятнашки». У цій задачі ми розглянемо простішу гру — «вісімки». Ігрове поле в цій грі має вигляд квадрата розміром 3 \times 3 клітини. Є $8$ квадратних фішок, пронумерованих цифрами від $1$ до $8$. Ці фішки у довільному порядку розташовані в клітинах поля. Одна клітина залишається вільною. За один хід можна перемістити у вільну клітину будь-яку з сусідніх фішок, тобто фішку, що стоїть праворуч чи ліворуч, або зверху чи знизу від вільної клітини. Мета гри — пересуваючи фішки по ігровому полю описаним вище способом, розставити всі фішки у правильному порядку:

$123$

$456$

$780$

Цифра $0$ позначає вільну клітину. Для заданого початкового розташування фішок потрібно визначити мінімальну кількість ходів, за яку можна розставити фішки у правильному порядку.