*程序的思想就是广度搜索,有一个技巧是把二维数组一维化,这样速度会快一些*/
#include <stdio.h>FILE *fp;
long count=1;
int [362880];/*记录这个状态是否出现过*/
int id,matrixl[2]={1,0};
int matrix[2][262880][10]={2,3,4,5,6,7,8,9,1,8};/*初始状态,1表示0,2表示1……,最后的8是指空格在数组的第8个位置*/
const int swpl[9]={2,3,2,3,4,3,2,3,2};/*空格在第N个位置时可以和几个位置的数交换*/
const int fact[9]={40320,5040,720,120,24,6,2,1,1};/*1-8的阶乘*/
const int swap[9][4]={{1,3},{0,2,4},{1,5},
        {0,4,6},{1,3,5,7},{2,4,8},
        {3,7},{4,6,8},{5,7}};/*空格在第N个位置,可以与它交换的是哪些位置*/long pos(int a[]){/*算这个状态(排列)对应数组中的第n个元素*/
  int i,j,k;
  long n=0;
  for (i=0;i<9;i++){
    for (j=0,k=1;j<i;j++)
      if (a[j]<a[i]) k++;
    n+=(a[i]-k)*fact[i];
  }
  return n;
}void print(int matrix[]){
  fprintf(fp,"%d %d %d\n",matrix[0]-1,matrix[1]-1,matrix[2]-1);
  fprintf(fp,"%d %d %d\n",matrix[3]-1,matrix[4]-1,matrix[5]-1);
  fprintf(fp,"%d %d %d\n\n",matrix[6]-1,matrix[7]-1,matrix[8]-1);
}void search(){
  int i,j,k,l,temp,id2,zero;
  long p;
  while (matrixl[id]){
    id2=(id+1)%2;
    for (j=0,l=0;j<matrixl[id];++j){
      zero=matrix[id][j][9];
      for (i=0;i<swpl[zero];++i){
        temp=matrix[id][j][zero];
        matrix[id][j][zero]=matrix[id][j][swap[zero][i]];
        matrix[id][j][swap[zero][i]]=temp;
        p=pos(matrix[id][j]);
        if (![p]){
          count++;
          [p]=1;
          print (matrix[id][j]);
          for (k=0;k<9;k++)
            matrix[id2][l][k]=matrix[id][j][k];
          matrix[id2][l++][9]=swap[zero][i];
        }
        temp=matrix[id][j][zero];
        matrix[id][j][zero]=matrix[id][j][swap[zero][i]];
        matrix[id][j][swap[zero][i]]=temp;
      }
    }
    id=(id+1)%2;
    matrixl[id]=l;
  }
}void main(){
  if ((fp=fopen("d:\\8.txt","w"))==NULL)
    return;
  [pos(matrix[0][0])]=1;
  print (matrix[0][0]);
  search();
  fprintf(fp,"%ld\n",count);
  printf("%ld\n",count);
  fclose (fp);
}