九宮排序問題:
在壹個方框中放上8個方塊,分別寫上1、2、3....8，另壹個位置空著，如圖所示。做此遊戲時，只能將與空格相鄰的方塊移入空格內。要求對任意給定的初始狀態，判斷是否能夠移成如圖的目標狀態所示，若能剛給出移動步伐，否則輸出不能信息。
初始圖：（0表示空格）
5 1 3
4 0 2
6 8 7
目標圖：
1 2 3
4 0 8
7 6 5
經典的廣度優先搜索問題，如果想要效率更高壹點可以采用雙向廣度優先搜索，不過總***才9!=362880種狀態，沒太大必要，偷懶不寫了
#include <iostream>
#define MAXN 362880
const int ftl[]={40320,5040,720,120,24,6,2,1,1};//階乘
const int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
//約定用三行三列的二維數組表示壹種狀態，其中用0表示空位
int Code(int a[3][3])//特定狀態轉化為編號
{
int A[9];
int i,j;
int ans;
ans=0;
for (i=0;i<9;i++) A[i]=a[i/3][i%3];
for (i=0;i<9;i++)
{
ans+=A[i]*ftl[i];
for (j=i+1;j<9;j++)
if (A[j]>A[i]) A[j]--;
}
return ans;
}
int head,tail;
int queue[MAXN][3][3];
int tar[3][3],tarid;
int pi[MAXN];//記錄隊列中各節點的前趨節點
bool hash[MAXN];
int length;
int path[MAXN];//記錄操作步驟
void Print(int i)//輸出步驟
{
int j,k;
length=0;
while (i!=-1)
{
path[length++]=i;
i=pi[i];
}
std::cout<<"Total steps: "<<length-1<<std::endl;
for (k=length-1;k>=0;k--)
{
std::cout<<"Step "<<length-k-1<<":"<<std::endl;
for (i=0;i<3;i++)
{
for (j=0;j<3;j++) std::cout<<queue[path[k]][i][j]<<' ';
std::cout<<std::endl;
}
}
return;
}
int main()
{
int i,j,k;
for (i=0;i<9;i++) std::cin>>queue[0][i/3][i%3];//約定輸入時用0表示空格，讀取初始狀態
for (i=0;i<9;i++) std::cin>>tar[i/3][i%3];//讀取目標狀態
tarid=Code(tar);
pi[0]=-1;
memset(hash,true,sizeof(hash));
hash[Code(queue[0])]=false;
head=0;
tail=1;
while (head<tail && hash[tarid])
{
int x,y;//當前節點中空格的位置
for (i=0;i<9;i++)
if (queue[head][i/3][i%3]==0)
{
x=i/3;
y=i%3;
break;
}
for (i=0;i<4;i++)
{
int x2,y2,id;//新生成節點的空格位置以及編號
x2=x+dir[i][0];
y2=y+dir[i][1];
if (x2>=0 && x2<3 && y2>=0 && y2<3)
{
for (j=0;j<9;j++) queue[tail][j/3][j%3]=queue[head][j/3][j%3];
queue[tail][x][y]=queue[tail][x2][y2];
queue[tail][x2][y2]=0;
id=Code(queue[tail]);
if (hash[id])
{
hash[id]=false;
pi[tail]=head;
if (id==tarid) Print(tail);
tail++;
}
}
}
head++;
}
if (hash[tarid]) puts("No Solution!");
return 0;
}