eight.cpp

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

// Eight.cpp : Defines the entry point for the console application.
//
//////////////////////////////////////////////////////////
//
//       文 件 名:    eight.cpp
//       创 建 者:    刘志祥
//       创建时间:    2004-5-31
//       功能描述:    利用广度优先搜索，求解八数码问题
//
/////////////////////////////////////////////////////////

#include "stdafx.h"
#include<iostream>
#include <iomanip>
#include<queue>
#include<algorithm>
using namespace std;



typedef struct
{
	int x;
	int y;
	int a[3][3];
	int state;
}Node;

struct Tree
{
	Node data;
	Tree *next;
};

Tree *head;

void print(Node *p)
{
	static int count=0;
	cout<<++count<<endl;
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
			cout<<setw(5)<<p->a[i][j];
		cout<<endl;
	}
	cout<<endl;
}

void Locatexy(Node s,int &x,int &y)      //此函数有待改进!!!!
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(s.a[i][j]==0)
			{
				 x=i;
				 y=j;
			}
}

bool Equal(Node s1,Node s2)       //判断两种状态是否相等
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(s1.a[i][j]!=s2.a[i][j])
				return false;
			 return true;
}
void LeftSwap(Node s1,int x,int y,Node &s2)
{
	s2=s1;
	swap(s2.a[x][y],s2.a[x][y-1]);
}
void UpSwap(Node s1,int x,int y,Node &s2)
{
	s2=s1;                            //最好定义一个拷贝构造函数
	swap(s2.a[x][y],s2.a[x-1][y]);
}
void RightSwap(Node s1,int x,int y,Node &s2)
{
	s2=s1;
	swap(s2.a[x][y],s2.a[x][y+1]);
}
void DownSwap(Node s1,int x,int y,Node &s2)
{
	s2=s1;
	swap(s2.a[x][y],s2.a[x+1][y]);
}
void ChangeState(Node begin,Node end)
{
	
	Tree *p0=new Tree;
	p0->data=begin;
	p0->next=NULL;
	queue<Tree *> q;
	q.push(p0);
	int x,y;
	while(!q.empty())
	{
		head=q.front();
		q.pop();
		Node s0=head->data;
	//	print(&s0);
		if(Equal(s0,end))
		{
			cout<<"succeed!"<<endl;
			break;
		}
		
        Locatexy(s0,x,y);
		if((x>0)&&(s0.state!=3))
		{
			Node s1;
			UpSwap(s0,x,y,s1);
			s1.state=1;
			Tree *p1=new Tree;
			p1->data=s1;
			p1->next=head;
			q.push(p1);
		}
		if((y>0)&&(s0.state!=4))
		{
			Node s2;
			LeftSwap(s0,x,y,s2);
			s2.state=2;
			
			Tree *p2=new Tree;
			p2->data=s2;
			p2->next=head;
			q.push(p2);
		}
		if((x<2)&&(s0.state!=1))
		{
			Node s3;
			DownSwap(s0,x,y,s3);
			s3.state=3;
			
			Tree *p3=new Tree;
			p3->data=s3;
			p3->next=head;
			q.push(p3);
		}
		if((y<2)&&(s0.state!=2))
		{
			Node s4;
			RightSwap(s0,x,y,s4);
			s4.state=4;
			
			Tree *p4=new Tree;
			p4->data=s4;
			p4->next=head;
			q.push(p4);
		}
	}
}
void Output(Tree *head)
{
	while(head->next)
	{
		print(&(head->data));
		head=head->next;
	}
}
int main(int argc, char* argv[])
{
	Node b,e;
	
	int i,j;
	int x,y;
	cout<<"请输入初始状态："<<endl;
	cout<<"Input:";
	for(i=0;i<3;i++)
		for( j=0;j<3;j++)
			cin>>b.a[i][j];
		cout<<"请结束初始状态："<<endl;
		cout<<"Input:";
		for( i=0;i<3;i++)
			for(j=0;j<3;j++)
				cin>>e.a[i][j];  
			
		print(&b);
	/*	Locatexy(b,x,y);
	//	cout<<x<<y<<endl;
		UpSwap(b,x,y,e);
		print(&e);
		RightSwap(b,x,y,e);
		print(&e);
		DownSwap(b,x,y,e);
		print(&e);
		LeftSwap(b,x,y,e);   */
		print(&e);
	//	if(Equal(b,e))
	//		cout<<1<<endl;
	//	else
	//		cout<<0<<endl;
		ChangeState(b,e);
		Output(head);
			return 0;
}