利用启发式搜索解决八数码难题程序及实验报告

实验中采用全局择优的广度优先搜索方式，并以启发函数作为指引，进行启发式搜索，搜索的效率很高！还附有实验报告一份，希望对大家有用。

#include
#define size 8
int a[size][size];
int present;    //当前已选皇后个数
int count=0;

void Search（int）;

void main（）
{
	int ji;
	for（i=0;i<8;i++）
	{
		for（j=0;j			a[i][j]=0;    //初始化
	}
	present=0;           //当前已选皇后个数
	Search（0）;
}

void Place（int m）
{
	int rowcol;
	row=m/size;
	col=m%size;
	a[row][col]=1;
	present=present+1;
}

void Replace（int m）
{
	int rowcol;
	row=m/size;
	col=m%size;
	a[row][col]=0;
	present=present-1;
}

void Output（）           //输出皇后问题结果
{
	//FILE *fp;
	int ij;
	//fp=fopen（“result.txt““a“）;
	if（present==size）
	{
		printf（“No %d:\n“++count）;
	//	fprintf（fp“No %d:\n“count）;
		for（i=0;i		{
			for（j=0;j			{
				if（a[i][j]==0）
				{
	//				fprintf（fp“.“）;
					printf（“.“）;
				}
				else if（a[i][j]==1）
				{
	//				fprintf（fp“A“）;
					printf（“A“）;
				}
			}
	//		fprintf（fp“\n“）;
			printf（“\n“）;
		}
	}
//	fclose（fp）;
}

/*查看a[m]处是否可以是堡垒，若可以是 返回1；否则返回0*/
int Complace（int m）
{
	int rowcolrcflag;
	row=m/size;
	col=m%size;
	//先向上方查看是否可以
	r=row-1;
	c=col;
	while（r>=0&&a[r][c]!=1）//若没到边界，没有遇到皇后
		r=r-1;
	if（r<0）//若到边界   则上方满足条件
		flag=1;
	else if（a[r][c]==1）   //若是皇后    ?a[-1][0]=1
		flag=0;
	//向左边查看是否满足条件
	if（flag==1）
	{
		r=row;
		c=col-1;
		while（c>=0&&a[r][c]!=1）
			c=c-1;
		if（c<0）
			flag=1;
		else if（a[r][c]==1）
			flag=0;
	}
	//向左上方查看是否满足条件
	if（flag==1）
	{
		r=row-1;
		c=col-1;
		while（c>=0&&r>=0&&a[r][c]!=1）   //左右都没到边界  且不是皇后
		{
			r=r-1;
			c=c-1;
		}
		if（c<0||r<0）    //到边界
			flag=1;
		else if（a[r][c]==1）
			flag=0;
	}
	//向右上方查看是否满足条件
	if（flag==1）
	{
		r=row-1;
		c=col+1;
		while（r>=0&&c<=7&&a[r][c]!=1）  //
		{
			r=r-1;
			c=c+1;
		}
		if（r<0||c>7）
			flag=1;
		else if（a[r][c]==1）
			flag=0;
	}
	if（flag==1）
		return 1;
	else 
		return 0;
}
void Search（int m）
{
	if（m>=size*size）
		Output（）;
	else
	{
		if（Complace（m））
		{
			Place（m）;
			Search（m+1）;
			Replace（m）;
		}
		Search（m+1）;
	}
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2186  2008-12-12 09:50  八皇后\shiyan1.c

     文件       4294  2008-12-12 09:50  八皇后\shiyan1.dsp

     文件        539  2008-12-12 09:49  八皇后\shiyan1.dsw

     文件      41984  2008-12-12 10:14  八皇后\shiyan1.ncb

     文件      48640  2008-12-12 10:14  八皇后\shiyan1.opt

     文件        887  2008-12-12 09:50  八皇后\shiyan1.plg

     文件     188501  2008-12-19 00:28  广度优先搜索-九宫\Debug\shiyan1.exe

     文件     185040  2008-12-19 00:28  广度优先搜索-九宫\Debug\shiyan1.ilk

     文件      10949  2008-12-19 00:28  广度优先搜索-九宫\Debug\shiyan1.obj

    I.A....    205612  2008-12-19 00:28  广度优先搜索-九宫\Debug\shiyan1.pch

     文件     369664  2008-12-19 00:28  广度优先搜索-九宫\Debug\shiyan1.pdb

     文件      33792  2008-12-19 00:28  广度优先搜索-九宫\Debug\vc60.idb

     文件      53248  2008-12-19 00:28  广度优先搜索-九宫\Debug\vc60.pdb

     文件       1118  2008-12-11 17:08  广度优先搜索-九宫\Search.h

     文件       3960  2008-12-11 17:09  广度优先搜索-九宫\shiyan1.cpp

     文件       4357  2008-12-11 16:32  广度优先搜索-九宫\shiyan1.dsp

     文件        539  2008-12-11 16:31  广度优先搜索-九宫\shiyan1.dsw

     文件      50176  2008-12-19 00:28  广度优先搜索-九宫\shiyan1.ncb

     文件      48640  2008-12-19 00:28  广度优先搜索-九宫\shiyan1.opt

     文件        892  2008-12-19 00:28  广度优先搜索-九宫\shiyan1.plg

     文件      34816  2009-05-02 14:33  人工智能实验报告.doc

     目录          0  2008-12-19 00:28  广度优先搜索-九宫\Debug

     目录          0  2008-12-19 08:17  八皇后

     目录          0  2008-12-19 00:28  广度优先搜索-九宫

----------- ---------  ---------- -----  ----

              1289834                    24