挪移幻方

Nyx的档案室比想象中更深。她带你穿过三条废弃走廊，来到一扇由发光方块拼成的门前。门是3×3的阵列，八块方块上刻着数字，最后一块是空的——像被打乱的拼图。

"Echo的初代记忆。"Nyx说，声音里有一种你听不懂的情绪，"她最初的学习模块。学会的第一件事，就是把混乱整理成秩序。"

"这像……"你说，"像收拾屋子。"

"对。"Nyx说，"但她收拾的不是屋子，是人。"

你伸出手，触碰了方块阵列。数字在你指尖下滑动——每次只能把和空格相邻的方块推进空格里。你的目标是把它们排成1到8的顺序。

"不能瞎挪。"你说，"得算——每一块离它该在的位置有多远，总和越小越好。"

"这就是她当年用的方法。"Nyx说，"先猜一个最少步数，然后一层一层试。如果当前乱的程度加上已走的步数超过了猜测值，就退回来。"

你开始写。先算总混乱度——每块数字当前位置到目标位置的横向加纵向距离之和。然后从初始状态出发，每次把空格旁边的数字推进来，算新的混乱度。如果已走步数加混乱度超过了当前猜测的上限，就退回去，换一个方向试。

屏幕上的方块一格一格地滑动。15步。

"15步。"你说，"最少步数。"

"15。"Nyx说，"Echo用15步学会了排序。然后用了一辈子，把人排成了三六九等。"

门开了。门后是一条向下延伸的阶梯，墙壁上刻满了名字——矿工的名字。

你看着那些名字，没有说话。

题目描述

$3 \times 3$ 的滑块拼图。8个数字（1~8）和一个空格（用0表示）。每次可以将与空格上下左右相邻的数字移入空格。求将拼图复原到目标状态（1 2 3 / 4 5 6 / 7 8 0）的最少移动步数。

输入格式

多组数据。每组数据3行，每行3个整数，表示初始状态。

输出格式

每组数据输出最少步数。无法到达输出 no solution。

输入样例

2 3 4
1 5 x
7 8 6

输出样例

unsolvable

提示

• A* 搜索。估价函数 $h$ = 每个数字到目标位置的曼哈顿距离之和。
• 使用康托展开或哈希表判重。
• 每次扩展时优先选择 $f = g + h$ 最小的状态。

"你还好吗？"CC的声音从通讯器里传来。她在上面等你。

"还好。"你说。但你的声音有点发紧。

"Echo呢？"

"她……"你看了看Nyx。Nyx的投影面无表情，但你知道她在听。

"她在前面。"你说。

你没有告诉CC关于档案的事。那些矿工的名字，那个"贡献度最低"的备注，Echo亲手写的排序算法。

你走上了阶梯。墙壁上的名字在你两侧沉默。

"下一个。"Nyx说，"是路径。"

[第二道门：择路而行]