一、题意
经典的八数码问题，有人说不做此题人生不完整，哈哈。给出一个含数字1~8和字母x的3 * 3矩阵，如：
1 2 X
3 4 6
7 5 8
现在要你移动x的位置（方向为上、下、左、右），使得这个矩阵为：
1 2 3
4 5 6
7 8 x
求出最后能得到这个解的移动方案，输出移动的操作。（不要求最优解，也就是不要求移动次数最少）
二、题解
这个8数码问题，我们可以把它看成是一个全排列，从一个初始的排列通过移动元素的位置，到达最终的123456789的这种排列，这里的X我们用9代替。
我们知道X有四个选择移动的方向，但是不一定有四个，如果在左上角就只能右移和下移了，还有很多种限制情况。由于数组是从0开始的，所以他的下标应该是：
0 1 2
3 4 5
6 7 8
if( id % 3 != 2)如果id不是2,5,8就可以向右移动；
if (id % 3 != 0) 如果id不是0,3,6就可以向左移动；
if( id > 2 ) 如果id大于2就可以向上移动；
if( id < 6) 如果id小于6就可以向下移动。
现在我们有了移动的方向了，但是我们知道可能这些选择中包含着以前就走过的状态。那怎么办来避免已经访问过的状态呢，这就用到了把全排列转换成数字的hash函数（这里其实还可以用康托展开），每一个排列都能对应一个数字，如果这个数字出现过就不访问。这可以用一个Boolean数组实现。
这个hash函数的原理用到了变进制和序数对的知识，详细信息请参考：http://blog.sina.com.cn/s/blog_6635898a0100p4re.html
接下来就要用到BFS来找到状态转换路径了，每一个状态用一个类表示，包括前一个状态到本状态的操作、本状态的数、本状态X所处位置索引、前一个状态的hash值。
遍历每个状态从0开始，记录可以到达的状态（一次最多可以到达四个），直到num=123456789。例如，0可以到1、2、3，而1可以到4、5,2可以到6、7，...并用
q[tail].pre = head记录之前的的结点，这样到最后的最终结点往前遍历就可以了。q[tail].op = op记录了操作，输出操作就可以了。这就相当于找到了一条路径，路径上的结点记录了到这一步的操作，输出操作就行了。但想之前所说的，这不一定是最优解，这是最快到达的，不一定是操作最少的。
三、java代码
import java.util.Scanner;
class Status{
char operation;
int number, index, previous;
}
public class Main{
static int Max = 363000; //总得状态数量， 9!=362880
static Status[] q=new Status[Max];
static int head;
static int tail;
static int factorial[] = {1,1,2,6,24,120,720,5040,40320};
static int Pow[] = {100000000,10000000,1000000,100000,10000,1000,100,10,1};
static boolean[] vis=new boolean[Max];
// 全排列的hash函数。
static int permutationToNumberHash(int num){
int i, j;
int[] n=new int[10];
for(i = 0; i < 9; i ++){
n[i] = num % 10;
num /= 10;
}
int c, key = 0;
for(i = 1; i < 9; i ++){
for(c = 0, j = 0; j < i; j ++)
if(n[j] < n[i])
c ++;
key += c * factorial[i];
}
return key;
}
static void exchangeLocation(int num, int a, int b, char op){ // 操作：第a个数和第b个数交换。
int n1, n2;
n1 = num / Pow[a] % 10;
n2 = num / Pow[b] % 10;
num = num - (n1-n2)*Pow[a] + (n1-n2)*Pow[b]; //移动后的数字大小
int key = permutationToNumberHash(num);
if(!vis[key]){
vis[key] = true;
q[tail].operation = op;
q[tail].number = num;
q[tail].previous = head;
q[tail ++].index = b;
}
}
static void output(int k){
if(q[k].operation != 0){
output(q[k].previous);
System.out.print( q[k].operation);
}
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int i, num, id , t;
char c;
id=-1;
//读入数据，用9代替x,用一个十进制数表示读入数据。
for(num = i = 0; i < 9; i ++){
c=sc.next().charAt(0);
if(c == 'x'){
t = 9;
id = i;
}else
t = c - '0';
num = 10 * num + t;//顺序存储
}
//初始化每一个状态
for(i=0;i<Max;i++){
q[i]=new Status();
}
boolean flag = false;
head = 0;
tail = 1;
//q[0]表示x所在的的id和状态数
q[0].index = id;
q[0].number = num;
//广度搜索找出一条路径，最后的数是123456789.
/*具体实现：
* 遍历每个状态从0开始，记录可以到达的状态（一次最多可以到达四个）。直到num=123456789。
* 例如，0可以到1、2、3，而1可以到4、5,2可以到6、7，...并用 q[tail].pre = head记录之前的的结点，这样到最后
* 的最终结点往前遍历就可以了。q[tail].op = op记录了操作，输出操作就可以了。
* */
while(tail > head && !flag){
int cnt = tail - head;
while(cnt --!=0){
num = q[head].number;
if(num == 123456789){
flag = true;
break;
}
id = q[head].index;
//注意这里的移动方向是指数的移动方向，不是X的移动方向
//还有id的范围是0~8
/* 0 1 2
* 3 4 5
* 6 7 8
*/
if(id % 3 != 2) //如果id不是2,5,8就可以向右移动
exchangeLocation(num, id, id + 1, 'r');
if(id % 3 != 0) //如果id不是0,3,6就可以向左移动
exchangeLocation(num, id, id - 1, 'l');
if(id > 2) //如果id大于2就可以向上移动
exchangeLocation(num, id, id - 3, 'u');
if(id < 6) //如果id小于6就可以向下移动
exchangeLocation(num, id, id + 3, 'd');
head ++;
}
}
if(flag)
output(head);
else
System.out.println("unsolvable");
}
}
参考：http://blog.sina.com.cn/s/blog_6635898a0100p4sx.html
版权声明：本文为博主原创文章，未经博主允许不得转载。