重排九宫

在分成9个小方格的盒子里，将1～8这8个数字任意安排，余下一个空格，与空格上、下、左、右相邻的数字可以移动。要求最后的数字从1至8按顺序排好，空格居于右下角。如图1-10所示，这就是重排九宫游戏。

图1-10

重排九宫是否有解？其准则和重排十五是一致的。在重排九宫有解的情况下，人们又欲寻找以最少的步数完成从初始状态到终局状态的转换。这是相当有难度的问题，例如求欲使图1-11中的数排成图1-10的顺序，其最少步数是多少？

图1-11

19世纪，英国趣味数学家杜丹尼找到一种36步的解答方法：12543， 12376，12376，12375，48123，65765，84785，6。该方法长期以来被认为是最佳答案，没有人提出质疑。直到后来借助于电子计算机，一下子找到10种30步的解答方法，才打破了杜丹尼的记录。这些解法如下：

① 12587，43125，87431，63152，65287，41256；

② 14587，53653，41653，41287，41287，41256；

③ 14314，25873，16312，58712，54654，87456；

④ 12587，48528，31825，74316，31257，41258；

⑤ 14785，24786，38652，47186，17415，21478；

⑥ 34785，21743，74863，86521，47865，21478；

⑦ 34785，21785，21785，64385，64364，21458；

⑧ 34521，54354，78214，78638，62147，58658；

⑨ 34521，57643，57682，17684，35684，21456；

⑩ 34587，51346，51328，71324，65324，87456。