8chess.cpp

人工智能算法 实现人工智能中的八数码问题

#include"8chess.h"


/***************************************************************************************
									主函数
****************************************************************************************/

void main()
{	
	int step=0;
	linklist Close;
	linklist Open;
	linklist path;
	int i;
	int initnum[9];
	int aimnum[9];
	cout<<"请输入初始状态：(空格用0表示)"<<endl;
	for(i=0;i<9;i++)
		cin>>initnum[i];
	cout<<"请输入目标状态：(空格用0表示)"<<endl;
	for(i=0;i<9;i++)
		cin>>aimnum[i];

	if(mazeequal(initnum,aimnum)==1)
	{
		cout<<"初始状态与目标状态相同！"<<endl;
		return;
	}

	if(Ifsolvable(initnum,aimnum)==0)
	{
		cout<<"不可解！"<<endl;
		return;
	}

	cout<<endl<<"搜索过程如下："<<endl;

	for(i=0;i<9;i++)
		init.maze[i] = initnum[i];
	init.g=0;
	Evaluate_locate0(init);
	Evaluate_f(init);

	for(i=0;i<9;i++)
		aim.maze[i] = aimnum[i];

	initlist(Open);
	initlist(Close);
	initlist(path);
	insertlist(Open,init);

	struct ElemType final;
	final=Search(Open,Close);
	insertlist(path,final);

	while(Isequal(final,init)!=1)
	{
		step++;
		lnode* temp;
		temp=Close;
		while(temp->next !=NULL)
		{
			temp=temp->next;
			if(mazeequal(temp->data.maze,final.father)==1)
				break;
		}
		final=fuzhi(temp->data);
		insertlist(path,temp->data);		
	}
	printlist(path);

	destroylist(Open);
	destroylist(Close);
	destroylist(path);
	cout<<"共"<<step<<"步"<<endl;
}

/*****************************************************************************************
								运行结果
******************************************************************************************/
/*
请输入初始状态：(空格用0表示)
1 2 3 4 5 6 7 8 0
请输入目标状态：(空格用0表示)
1 2 3 0 4 5 6 7 8

搜索过程如下：
1  2  3
4  5  6
7  8


1  2  3
4  5  6
7     8


1  2  3
4  5  6
   7  8


1  2  3
   5  6
4  7  8


1  2  3
5     6
4  7  8


1  2  3
5  6
4  7  8


1  2  3
5  6  8
4  7


1  2  3
5  6  8
4     7


1  2  3
5     8
4  6  7


1  2  3
   5  8
4  6  7


1  2  3
4  5  8
   6  7


1  2  3
4  5  8
6     7


1  2  3
4  5  8
6  7


1  2  3
4  5
6  7  8


1  2  3
4     5
6  7  8


1  2  3
   4  5
6  7  8


共15步
Press any key to continue



请输入初始状态：(空格用0表示)
2 8 3 1 6 4 7 0 5
请输入目标状态：(空格用0表示)
1 2 3 8 0 4 7 6 5

搜索过程如下：
2  8  3
1  6  4
7     5


2  8  3
1     4
7  6  5


2     3
1  8  4
7  6  5


   2  3
1  8  4
7  6  5


1  2  3
   8  4
7  6  5


1  2  3
8     4
7  6  5


共5步
Press any key to continue




请输入初始状态：(空格用0表示)
1 2 3 4 5 6 7 8 0
请输入目标状态：(空格用0表示)
1 2 3 0 8 7 6 4 5
不可解！
Press any key to continue
*/