procmtd.cpp

八数码问题的求解八数码问题的求解八数码问题的求解八数码问题的求解

// ProcMtd.cpp: implementation of the ProcMtd class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Eight.h"
#include "ProcMtd.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////



ProcMtd::ProcMtd(NineBox* box)
{
	this->question_solved=false;
	this->box=box;
	OK1=OK2=OK3=OK4=OK5=OK6=OK7=false;step=step2=0;
	Skep_3=Skep_5=false;
}

ProcMtd::~ProcMtd()
{

}

int ProcMtd::solve()
{
	if(!box) return 0;
	int ir=0;
	

	if(!ProcMtd::OK1)
		ir=Set_1();
	if(ir==0 && !OK2)
		ir=Set_2();
	


	if(!Skep_3)
	{
		if(ir==0 && !OK3)
			ir=Set_3();
		if(ir==0 && !OK4)
			ir=Set_4();
	}

	if(ir==0 && !OK5)//set '4'
		ir=Set_5();

	if(!Skep_5)
	{
		if(ir==0 && !OK6)
			ir=Set_6();

		if(ir==0 && !OK7)
			ir=Set_7();
	}
	if(ir==0)
		ir=Set_8();

	return ir;
}

int ProcMtd::Set_8()
{
	static int pos[4][2]={1,0, 2,0, 2,1, 1,1};
	static int moving[4]={2,  4,   1,   3};

	int ir=0;
	int x,y,m,n,j,k;
	int i;
	box->GetXYByValue(6,x,y);
	box->GetXYByValue(7,m,n);
	box->GetXYByValue(8,j,k);
	if(x==2 && y==1 && m==2 && n==0 &&j==1 && k==0)
	{
				return 0;
	}
	else
		box->GetXYByValue(0,x,y);
	for(i=0;i<4;i++)
	{
		if(pos[i][0]==x && pos[i][1]==y) 
			break;
	}

	return moving[i];
}
int ProcMtd::Set_7()
{
	static int pos[12][2]={1,0, 0,0, 0,1, 0,2, 1,2, 1,1, 2,1, 2,2, 1,2, 0,2, 0,1, 0,0};
	static int moving[12]={1,4,4,2,3,2,4,1,1,3,3,2};

	if((ProcMtd::step2)==12 || OK7)
	{
		ProcMtd::OK7=true;
		return 0;
	}
	step2++;
	return moving[ProcMtd::step2-1];
}

int ProcMtd::Set_6()
{
	static int pos[4][2]={1,0, 2,0, 2,1, 1,1};
	static int moving[4]={2,  4,   1,   3};
	if(OK6) 
		return 0;

	int ir=0;
	int x,y;x=y=0;
	int i;
	box->GetXYByValue(5,x,y);
	if(x==1 && y==1) 
	{
		OK6=true;
		return 0;
	}
	else
		box->GetXYByValue(0,x,y);
	for(i=0;i<4;i++)
	{
		if(pos[i][0]==x && pos[i][1]==y) 
			break;
	}

	return moving[i];
}
int ProcMtd::Set_5()
{
	static int pos[6][2]={1,0, 2,0, 2,1, 2,2, 1,2, 1,1};
	static int moving[6]={2,  4,   4,   1,   3,   3};
	if(OK5) 
		return 0;

	int ir=0;
	int x,y;x=y=0;
	int i;
	box->GetXYByValue(4,x,y);
	if(x==1 && y==2) 
	{
		OK5=true;
		//if skep '5'?
		box->GetXYByValue(5,x,y);
		if(x==2 && y==2) Skep_5=true;
		return 0;
	}
	else
		box->GetXYByValue(0,x,y);
	for(i=0;i<6;i++)
	{
		if(pos[i][0]==x && pos[i][1]==y) 
			break;
	}

	return moving[i];
}
int ProcMtd::Set_4()
{
	static int pos[8][2]={1,0, 0,0, 0,1, 1,1, 1,2, 0,2, 0,1, 0,0};
	static int moving[8]={1,   4,   2,   4,   1,   3,   3,   2};

	if((ProcMtd::step)==8 || OK4)
	{
		OK4=true;
		return 0;
	}
	step++;
	return moving[ProcMtd::step-1];
}

int ProcMtd::Set_3()
{
	static int pos[6][2]={1,0, 2,0, 2,1, 2,2, 1,2, 1,1};
	static int moving[6]={2,  4,   4,   1,   3,   3};
	if(OK3) 
		return 0;

	int ir=0;
	int x,y;x=y=0;
	int i;
	box->GetXYByValue(3,x,y);
	if(x==1 && y==1) 
	{
		OK3=true;
		return 0;
	}
	else
		box->GetXYByValue(0,x,y);
	for(i=0;i<6;i++)
	{
		if(pos[i][0]==x && pos[i][1]==y) 
			break;
	}

	return moving[i];
}
int ProcMtd::Set_2()
{
	static int pos[8][2]={0,1, 1,1, 1,0, 2,0, 2,1, 2,2, 1,2, 0,2};
	static int moving[8]={2,   3,   2,   4,   4,   1,   1,   3};
	if(OK2) return 0;
	int ir=0;
	int x,y;x=y=0;
	int i;
	box->GetXYByValue(2,x,y);
	if(x==0 && y==1) 
	{
		OK2=true;
		//if skep '3'?
		box->GetXYByValue(3,x,y);
		if(x==0 && y==2) Skep_3=true;
		return 0;
	}
	else
		box->GetXYByValue(0,x,y);
	for(i=0;i<8;i++)
	{
		if(pos[i][0]==x && pos[i][1]==y) 
			break;
	}

	return moving[i];
}

int ProcMtd::Set_1()
{
	static int pos[8][2]={0,0,1,0,2,0,2,1,2,2,1,2,1,1,0,1};
	static int moving[8]={2,2,4,4,1,3,1,3};
	if(OK1) return 0;
	int ir=0;
	int x,y;x=y=0;
	int i;
	box->GetXYByValue(1,x,y);
	if(x==0 && y==0) 
	{
		OK1=true;
		return 0;
	}
	else
		box->GetXYByValue(0,x,y);
	for(i=0;i<8;i++)
	{
		if(pos[i][0]==x && pos[i][1]==y) break;
	}

	return moving[i];
}

int ProcMtd::Init()
{
	if(!box) return 0;

	bool _m,_n;
	_m=_n=false;
	int x,y;
	x=y=0;
	box->GetXYByValue(0,x,y);
	if(x==0 && y==2) _m=true;
	box->GetXYByValue(1,x,y);
	if(x==0 && y==2) _n=true;

	if(_m)//空格在位置C上
	{
		return 3;//	<-：空格左移
	}
	if(_n)//“1”在C(0,2)上，让空格到F(1,2)，空格上移
	{
		int p_x,p_y;//空格位置
		box->GetXYByValue(0,p_x,p_y);

		//p_x---->1
		if(p_x==0) return 2;//下
		if(p_x==2) return 1;//上

		//p_y---->2
		if(p_y<2) return 4;//右

		return 1;
	}
	return 0;
}