题目描述

dash最近迷上了一个叫八数码的游戏，如下图 $1$，在 $3 \times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移动空格中。

游戏的目标是通过棋子的移动使 $8$ 个棋子到达图 $2$ 的布局。