资 源 简 介
最近巴达兽在研究一个数码问题:在一个 1*9 的棋盘上,摆着 8 个棋子,每个棋子标有
1 至 8 的某个数字,不同的棋子标的数字不同,棋盘还有一个空格,假设空格的位置为 x(位
置从 1 到 9),那么如果棋子的坐标 y, |y-x|<=3 的时候,可以把这个棋子移动到空格的地
方,现在我们给出初始状态和目标状态,我们都知道传统的数码问题是要找出一种从初始状
态转换成目标状态的最少移动步数,现在为了简化这个问题,我们做了一些改变,首先,我
们认为两个状态是等价的只要他满足以下的条件:
· 把两个状态中的空格位置拿掉之后是相同的则认为两个状态是等价的,如
“ 123_45678”和“ 1_2345678”,“ 12345678_” (“ _” 表示空格)都是等价的。
现在我们想知道从初始状态, 转化成目标状态(或者目标状态的一个等价状态)的最小
移动步数。