八數位問題——回溯法

将棋盤狀态用一維數組表示

如下圖，初始狀态表示為 “283164705”

算法思想：

 使用回溯法。

 按照目前布局進行DFS搜尋，以目前布局是否出現過進行剪枝對象。

#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include <iostream>
#include<stack>
using namespace std;
map<string,bool> state_record;//用于記錄狀态是否出現過
typedef struct 
{
	string num;//排列
	int pos;//排列中空的位置
}node;
int depth=7;//限制搜尋深度
int changeId[9][4]={{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},

					{0,-1,6,4},{1,3,7,5},{2,4,8,-1},

					{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}

					};//0出現在0->8的位置後該和哪些位置交換 

string des="123804765";
void swap(string &s,int a,int b)//交換字元串中的兩個位置 
{
	char t=s[a];
	s[a]=s[b];
	s[b]=t;
}
void print(stack<node> res)//列印最後結果
{
	string cur;//用于儲存目前狀态的字元串
	stack<node> res1;
	while(!res.empty())
	{
		node t=res.top();
		res.pop();
		res1.push(t);
	}
	while(!res1.empty ())
	{
		node t=res1.top();
		res1.pop();
		cur=t.num;
	    for(int i=0;i<9;i++)
	    {
		   if(cur[i]=='0')
			   cout<<"   ";
		   else
		      cout<<cur[i]<<"  ";
		   if((i+1)%3==0)
			   cout<<endl;
		}
		cout<<"→"<<endl;
	}
}
void dfs(string n,int p,stack<node> res)
{
	if(res.size()>=depth)
		return;
	node new_node;
	new_node.num =n;
	new_node.pos =p;
	string cur=n;//用于儲存目前狀态的字元串 
	for(int i=0;i<4;i++)//擴充目前的狀态，上下左右四個方向
	{ 
		int swapTo=changeId[new_node.pos][i];//将要和那個位置交換
		if(swapTo!=-1)//-1則不交換 
		{
			swap(cur,p,swapTo);//交換0的位置得到新狀态
			if(cur==des)//目标狀态
	        {
			   stack<node> t;
			   t=res;
			   node t1;
			   t1.num =cur;
			   t.push(t1);
			   print(t);//列印目标狀态
			   return;
            }
			if(state_record.count(cur)==0)//該狀态未出現過，則将該狀态入棧
			{
				state_record[cur]=1;
				node n_node;
				n_node.num =cur;
				n_node.pos =swapTo;
				res.push(n_node);
				dfs(cur,swapTo,res);
				res.pop();
			}
			swap(cur,p,swapTo);
		}
		
	}
	return;
}

int main(){
	string start; 
	int i=-1;
	cin>>start;
	while(start[++i]!='0');//查找初始狀态0的位置  
	stack<node> res;
	node new_node;
	new_node.num =start;
	new_node.pos =i;
	res.push(new_node);
	state_record[start]=1;
	if(start!=des)//判斷輸入狀态是否就是目的狀态 
		dfs(start,i,res); 
	return 0;

}