chess.cpp

任意相互不捕捉皇后生成源程序（类似相互不捕捉八皇后）

// Chess.cpp: implementation of the CChess class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "atqueue.h"
#include "Chess.h"

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

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

CChess::CChess()
{
	N = 0;
	DispNo = 0;
}

CChess::~CChess()
{
	CChessFree();
}

void CChess::CChessMalloc()
{
	TRACE("void CChess::CChessMalloc()\n");
	Grid = new char*[N];
	for(int i = 0;i<N;i++)
		Grid[i] = new char[N]; 
	for(i = 0;i<resCount;i++)
	{
		res[i] = new int[N];
	}
	resOne = new int[N];
}

void CChess::CChessFree()
{
	TRACE("void CChess::CChessFree()\n");

	for(int i = 0;i<N;i++)
		delete [] Grid[i];
	delete [] Grid;
	for(i = 0;i<resCount;i++)
	{
		delete [] res[i];
	}
	delete [] resOne;
}

void CChess::go()
{
	TRACE("void CChess::go()\n");

	DispNo = 0;
	DispNoMax = 0;
	
	//CChessFree();
	CChessMalloc();	
	for(int k = 0;k<resCount;k++)
	for(int j = 0;j<N;j++)
	{
		res[k][j] = -1;
	}


	bool condition = true;
	int i = 0;

	
	int resPos = 0;
	for(int t = 0;t<N;t++)
		resOne[t] = -1;

	i = 0;
	resOne[0] = 0;
	do
	{		
		if(condition)
		{
			if(i<N-1)
			{
				i++;
				resOne[i] = 0;
				condition = CChessCapture();
			}
			else //i == N-1
			{
				//回溯
				while(resOne[i]==N-1)
				{
					resOne[i]  = -1;
					i--;
				}
				resOne[i]++;
				condition = CChessCapture();
			}			
		}
		else//condition == false
		{
			//回溯
			while(resOne[i]==N-1)
			{
				resOne[i]  = -1;
				i--;
			}
			resOne[i]++;
			condition = CChessCapture();
		}	
		
		//输出
		if(condition&&i==N-1)
		{			
			for(int k = 0;k<N;k++)
				res[resPos][k] = resOne[k];
			resPos++;
			DispNoMax = resPos;
		}

		
	}
	while(!(i==0&&resOne[0]==N-1));
	
}

bool CChess::CChessCapture()
{

	TRACE("void CChess::CChessCapture()\n");

	int row = 0;

	for(int i = 0;i<N;i++)
	{
		if(resOne[i] !=-1)
		{
			row = i-1;
			break;
		}
	}
	if(i == N)
		row = N;
	
	bool bSuccess = true;

	//列比较
	for( i = 0;i<N-1;i++)
		for(int j = i+1;j<N;j++)
		{
			if(resOne[i] == resOne[j]&&resOne[i]!=-1)
				return false;//表示有捕捉
		}

	//斜比较
	for(int t = 2;t<N+1;t++)
		for(int i = 0;i<t-1;i++)
			for(int j = i+1;j<t;j++)
				if(resOne[N - t-i]+j == resOne[N-t-j]+i&&resOne[N - t-i]!=-1)
					return false;

	for(t =0;t<N-2;t++)
		for(int i = 0;i<N-t-1;i++)
			for(int j=i+1;j<N-t;j++)
				if(resOne[i]-i == resOne[j]-j&&resOne[i]!=-1)
					return false;

	//反斜比较
	for(t=2;t<N+1;t++)
		for(int i=0;i<t-1;i++)
			for(int j=i+1;j<t;j++)
				if(resOne[t-i]+j == resOne[t-j]+i&&resOne[t-i]!=-1)
					return false;

	for(t =0;t<N-2;t++)
		for(int i = 0;i<t-1;i++)
			for(int j=i+1;j<t;j++)
				if(resOne[N-i]+j == resOne[N-j]+i&&resOne[N-i]!=-1)
					return false;

	return bSuccess;
}

void CChess::Draw(CDC* pDC)
{
	if(N==0)
		return;
	
	int scale = 50;
	for(int t = 0;t<=N;t++)
	{
		CPoint pt1(0,t*scale);
		pt1.x += 10;
		pt1.y += 10;
		pDC->MoveTo(pt1);
		pt1.x = N*scale;
		pt1.x += 10;
		pDC->LineTo(pt1);
	}

	for( t = 0;t<=N;t++)
	{
		CPoint pt1(t*scale,0);
		pt1.x += 10;
		pt1.y += 10;
		pDC->MoveTo(pt1);
		pt1.y = N*scale;
		pt1.y += 10;
		pDC->LineTo(pt1);
	}	

	//清空
	for(t = 0;t<N;t++)
		for(int k = 0;k<N;k++)
			Grid[t][k]= ' ';

	//显示
	if(DispNo == DispNoMax )
	{
		CString mstr;
		mstr.Format("%d",DispNoMax);
		mstr = "max:"+mstr+". re start";
		AfxMessageBox(mstr);
		DispNo = 0;		
	}
	for(int i = 0;i<N;i++)
		if(res[DispNo][i]!=-1)
			Grid[i][res[DispNo][i]] ='Q';

	for(t = 0;t<N;t++)
		for(int i = 0;i<N;i++)
		{
			pDC->DrawText(Grid[t][i],
				CRect(CPoint(10+t*scale,20+i*scale),CSize(scale,scale)),
				DT_NOCLIP|DT_CENTER);//|DT_VCENTER
		}	
}