算法说明.txt

利用BFS算法解八数码问题 在3*3的方格上放着1-8数码

                               利用BFS算法解八数码问题
  在3*3的方格上放着1-8数码，有一空格为0变化规则为空格可以和上，下，右，左四个相邻的数字互换，
至到和目标状态相等，
每一种状态用一个结点表示
而每个结点每次变化最多有四种结点，将这些结点依次入队列中，
例如初始结点S0,入队列后出队，将S0变化最多产生的四种结点S01,S02,S03,S04依次入队列中，
当S01出队后，产生的四种结点S11，S12，S13，S14(实际上不会有四种结点)依次入队，
每次出队时与结束结点相比较，如果相等则退出，
为了，防止已经入队的结点再次入队，(这样会造成列循环),将每次入队的结点设置一个标识号，
四种变化即:向上，向下，向右，向左，我们要求向上和向下互斥，向右和向左互斥

  取空格的坐标(x,y)

  if(x>0)   向上变化，入队，设置标识1,    UpSwap()
  if(y>0)   向左变化，入队，设置标识2，   LeftSwap()
  if(x<m-1) 向下变化，入队，设置标识3,    DownSwap()
  if(y<m-1) 向右变化，入队，设置标识4，   RightSwap()

  这样得到为一棵树，现在要考虑的是这棵树的高度，

现在要解决的问题是如何得到的变化结果的路径打印出来!!!!

   数据结构  
结点
struct Node
{
   int a[3][3];
   int x;
   int y;
}
队列
   queue<Node>  q;
树(逆向树)
 struct  Tree
{
   Node data;
   Tree *next;
}
试图在结点进入队列中建立逆向树
但是不能把树建立起来，只要考虑把这种放入队列中，


2004-5-31经过艰苦的努力，程序终于成功运行，并取得很的成绩
而且能够将变换结果打印出来！！



附测试数据
  2 8 3                 1 2 3
  1 0 4       变成      8 0 4 
  7 6 5                 7 6 5