八数码问题.cpp

用C++语言实现的八数码问题

// 八数码问题.cpp : 定义控制台应用程序的入口点。
//该程序的运行环境为Microsoft Visual Studio 2008。

#include "stdafx.h"
#include<iostream>
#include<ostream>
#include<vector>
using std::cin;
using std::cout;
using std::endl;
using std::ostream;
using std::vector;

const int row=3;
const int col=3;
const int maxDistance=1000;
const int maxNum=1000;

typedef struct _Node{
	int digit[row][col];    //     记录每步的状态
	int dist;               //     记录与目标状态的“距离”，计算公式为每个点现在在的位置与其应该在的位置的距离之和。
	int deep;               //     记录搜索深度，启发信息为f(n)＝dist+deep；
	int index;              //     记录父节点
} Node;

Node source;               //      初始状态
Node aim;                  //      目标状态
vector<Node> node_v;       //      记录搜索路径

//交换函数
void exchange(int& a,int& b){
	int temp;
	temp=a;
	a=b;
	b=temp;
}
//求绝对值
int fabs(int a){
	return a>0?a:-a;
}
//判断是否有节点可以扩展，没有测说明无解
bool isEmptyOfOpen(){
	for(int i=0;i!=node_v.size();++i)
		if(node_v[i].dist+node_v[i].deep<maxNum)
			return false;
	return true;
}
//检测函数，看是否有解
bool check(){
	int x1,y1;         //   记录横坐标
	int x2,y2;         //   记录纵坐标
	int count_1,count_2;
	for(int i=0;i!=row&&!flag;++i){
		for(int j=0;j!=col;++j){
			if(source.digit[i][j]==0){
				x1=i;
				y1=j;
			}
			if(aim.digit[i][j]==0){
				x2=i;
				y2=j;
			}
		}
	}
		

//判断两状态是否形同
bool isEqual(int index,int digit[][col]){
	for(int i=0;i!=row;++i)
		for(int j=0;j!=col;++j){
			if(node_v[index].digit[i][j]!=digit[i][j])
				return false;
		}
	return true;
}
//复制
void assign(Node& node,int index){
	for(int i=0;i!=row;++i)
		for(int j=0;j!=col;++j)
			node.digit[i][j]=node_v[index].digit[i][j];
}
//求某个状态到目标状态的距离
int Distance(Node& node,int digit[][col]){
	int dis=0;
	bool flag=false;
	for(int i=0;i!=row;++i)
		for(int j=0;j!=col;++j)
			for(int k=0;k!=row;++k){           
				for(int m=0;m!=col;++m){
					if(node.digit[i][j]==digit[k][m]){
						dis+=fabs(i-k)+fabs(j-m);
						flag=true;
						break;
					}
					else
						flag=false;
					if(flag)
						break;
				}
			}
	return dis;
}
//判断是否可以拓展，即判断该状态是否与以前的某个状态相重复
bool isExpandable(Node& node){
	for(int i=0;i!=node_v.size();++i)
		if(isEqual(i,node.digit))
			return false;
	return true;
}
//寻找最优的扩展点
int getBestNode(){
	int dist=maxNum;
	int loc;                  
	for(int i=0;i!=node_v.size();++i){
		if(node_v[i].dist==maxNum)
			continue;
		else if(node_v[i].dist+node_v[i].deep<dist){
			loc=i;
			dist=node_v[i].dist+node_v[i].deep;
		}
	}
	return loc;
}
//进行扩展
void processNode(int index){
	//先找到空客（即用0标记的位置）
	int x;         //   记录横坐标
	int y;         //   记录纵坐标
	bool flag=false;
	for(int i=0;i!=row&&!flag;++i){
		for(int j=0;j!=col;++j)
			if(node_v[index].digit[i][j]==0){
				x=i;
				y=j;
				flag=true;
			}
	}
	//向上扩展
	if(x>0){
		Node node_up;
		int dist_up;
	    assign(node_up,index);
	    exchange(node_up.digit[x][y],node_up.digit[x-1][y]);
		if(isExpandable(node_up)){
			dist_up=Distance(node_up,aim.digit);             //计算该拓展节点与目标点的距离 
			node_up.index=index;
			node_up.dist=dist_up;
			node_up.deep=node_v[index].deep+1;
			node_v.push_back(node_up);                
		}
	}
	//向下扩展
	if(x<2){
		Node node_down;
		int dist_down;
		assign(node_down,index);
		exchange(node_down.digit[x][y],node_down.digit[x+1][y]);
		if(isExpandable(node_down)){
			dist_down=Distance(node_down,aim.digit);
			node_down.index=index;
			node_down.dist=dist_down;
			node_down.deep=node_v[index].deep+1;
			node_v.push_back(node_down);
		}
	}
	//向左扩展
	if(y>0){
		Node node_left;
		int dist_left;
		assign(node_left,index);
		exchange(node_left.digit[x][y],node_left.digit[x][y-1]);
		if(isExpandable(node_left)){
			dist_left=Distance(node_left,aim.digit);
			node_left.index=index;
			node_left.dist=dist_left;
			node_left.deep=node_v[index].deep+1;
			node_v.push_back(node_left);
		}
	}
	//向右扩展
	if(y<2){
		Node node_right;
		int dist_right;
	    assign(node_right,index);
		exchange(node_right.digit[x][y],node_right.digit[x][y+1]);
		if(isExpandable(node_right)){
			dist_right=Distance(node_right,aim.digit);
			node_right.index=index;
			node_right.dist=dist_right;
			node_right.deep=node_v[index].deep+1;
			node_v.push_back(node_right);
		}
	}
	node_v[index].dist=maxNum;
}
//重载输出流
ostream& operator<<(ostream& out,Node& node){
	for(int i=0;i!=row;++i){
		for(int j=0;j!=col;++j)
			out<<node.digit[i][j]<<"  ";
		out<<endl;
	}
	return out;
}
//输出搜索过程
void display(int index,vector<Node>& rstep_v){
	rstep_v.push_back(node_v[index]);
	index=node_v[index].index;
	while(index!=0){
		rstep_v.push_back(node_v[index]);
		index=node_v[index].index;
	}
	for(int i=rstep_v.size()-1;i!=0;--i){
		cout<<"step "<<rstep_v.size()-i<<endl;
		cout<<rstep_v[i]<<endl;
	}
	cout<<"得到目标状态为："<<endl;
	cout<<rstep_v[0]<<endl;
	cout<<"最少需要 "<<rstep_v.size()<<" 步"<<endl;
}
//主函数测试
int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"请输入初始状态，0代表空格："<<endl;
	for(int i=0;i!=row;++i)
		for(int j=0;j!=col;++j)
			cin>>source.digit[i][j];
	source.deep=1;
	source.dist=0;
	source.index=0;
	cout<<"请输入目标状态，0代表空格："<<endl; 
	for(int i=0;i!=row;++i)
		for(int j=0;j!=col;++j)
			cin>>aim.digit[i][j];
	node_v.push_back(source);
	cout<<"搜索中，请等待……"<<endl;
	while(true){
		if(isEmptyOfOpen()){
			cout<<"不能从初始状态到达目标状态！"<<endl;
			return -1;
		}
		else{
			int loc;
			loc=getBestNode();
			if(isEqual(loc,aim.digit)){
				vector<Node> rstep_v;
				cout<<"初始状态："<<endl;
				cout<<source<<endl;
				display(loc,rstep_v);
				break;
			}
			else
				processNode(loc);
		}
	}
	return 0;
}