关灯游戏求解算法含代码

本程序为求解关灯游戏的算法,同时还有一个测试程序,

/*
此程序为求关灯游戏的解的程序
经过测试关灯游戏的解不唯一.
*/
#include
using namespace std;
bool test（int* &rectfirstint* &rectsecondint &mint &nint* &wint &location）
{//回溯法的剪枝函数
	int ij;
	if（location==m*n-1）
		for（i=0;i		{
			if（rectfirst[i]!=rectsecond[i]）
				return false;
		}
	else
	{
		j=location-n;
		if（j<0）
			return true;
		else 
			return rectfirst[j]==rectsecond[j];
	}
	return true;
}

void add（int* &rectsecondint &mint &nint* &wint &locationint i）
{
	location++;
	if（i==0）
		w[location]=0;
	else
	{
		w[location]=1;
		if（location-n>=0）
			rectsecond[location-n]=1-rectsecond[location-n];
		if（location%n>0）
			rectsecond[location-1]=1-rectsecond[location-1];
		rectsecond[location]=1-rectsecond[location];
		if（（location+1）%n>0）
			rectsecond[location+1]=1-rectsecond[location+1];
		if（location+n			rectsecond[location+n]=1-rectsecond[location+n];
	}
}

void resume（int* &rectsecondint mint nint* &wint &locationint i）
{
	if（i==1）
	{
		if（location-n>=0）
			rectsecond[location-n]=1-rectsecond[location-n];
		if（location%n>0）
			rectsecond[location-1]=1-rectsecond[location-1];
		rectsecond[location]=1-rectsecond[location];
		if（（location+1）%n>0）
			rectsecond[location+1]=1-rectsecond[location+1];
		if（location+n			rectsecond[location+n]=1-rectsecond[location+n];
	}
	location--;
}
bool search（int* &rectfirstint* &rectsecondint &mint &nint* &wint &location）
{//此函数中的add和resume的参数0 1 更改会影响找到的解（因为解不唯一）
	if（location==m*n-1）
		return true;
	add（rectsecondmnwlocation0）;
	if（test（rectfirstrectsecondmnwlocation）==false||search（rectfirstrectsecondmnwlocation）==false）
	{
		resume（rectsecondmnwlocation0）;
		add（rectsecondmnwlocation1）;
		if（test（rectfirstrectsecondmnwlocation）==false||search（rectfirstrectsecondmnwlocation）==false）
		{
			resume（rectsecondmnwlocation1）;
			return false;
		}
	}
	return true;
}
/*
bool search（int* &rectfirstint* &rectsecondint &mint &nint* &wint &location）
{//此函数中的add和resume的参数0 1 更改会影响找到的解（因为解不唯一）
	if（location==m*n-1）
		return true;
	add（rectsecondmnwlocation1）;
	if（test（rectfirstrectsecondmnwlocation）==false||search（rectfirstrectsecondmnwlocation）==false）
	{
		resume（rectsecondmnwlocation1）;
		add（rectsecondmnwlocation0）;
		if（test（rectfirstrectsecondmnwlocation）==false||search（rectfirstrectsecondmnwlocation）==false）
		{
			resume（rectsecondmnwlocation0）;
			return false;
		}
	}
	return true;
}
	*/
int main（）
{
	int *rectfirst*rectsecondm=0n=0*wlocation=-1;
	int ij;
	//rect 存放二维数组m n为二维数组的行列w存放结果 location为w的有效数据个数
	cout<<“此程序为求关灯游戏的一个可行解“<	do
	{
		m=0;
		n=0;
		location=-1;
		while（m<=0||n<=0）
		{
			cout<<“请输入行数和列数:“<			cin>>m>>n;
		}
		rectfirst= new int[m*n];
		rectsecond= new int[m*n];
		w= new int[m*n];
		cout<<“请输入灯的状态 1为亮 0为灭:“<		for（i=0;i			for（j=0;j

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

     文件         49  2009-08-19 21:29  说明.txt

     文件       3594  2009-08-02 10:11  AllOut\AllOut.cpp

     文件       4284  2009-07-31 12:32  AllOut\AllOut.dsp

     文件        520  2009-07-31 11:37  AllOut\AllOut.dsw

     文件      41984  2009-08-02 10:13  AllOut\AllOut.ncb

     文件      53760  2009-08-02 10:13  AllOut\AllOut.opt

     文件       1258  2009-08-02 10:11  AllOut\AllOut.plg

     文件       1527  2009-07-31 16:06  AllOut\Debug\a.obj

     文件          0  2009-07-31 16:06  AllOut\Debug\a.sbr

     文件     443392  2009-07-31 16:18  AllOut\Debug\AllOut.bsc

     文件     557107  2009-08-02 10:11  AllOut\Debug\AllOut.exe

     文件     800592  2009-08-02 10:11  AllOut\Debug\AllOut.ilk

     文件     253625  2009-08-02 10:11  AllOut\Debug\AllOut.obj

     文件    2001156  2009-08-02 10:09  AllOut\Debug\AllOut.pch

     文件    1123328  2009-08-02 10:11  AllOut\Debug\AllOut.pdb

     文件          0  2009-07-31 16:18  AllOut\Debug\AllOut.sbr

     文件      91136  2009-08-02 10:11  AllOut\Debug\vc60.idb

     文件     118784  2009-08-02 10:11  AllOut\Debug\vc60.pdb

     文件          0  2009-07-31 18:41  AllOut\关灯游戏.txt

     文件     205746  2008-04-22 17:17  关灯游戏.swf

     目录          0  2009-08-19 21:27  AllOut\Debug

     目录          0  2009-08-19 21:27  AllOut

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

              5701842                    22