queens.cpp

经典的八皇后问题

// Queen.cpp: implementation of the CQueen class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include <stdio.h >
#include "stdlib.h"
#include <conio.h >
#include <math.h >
#include "Queens.h"
#include "Queen.h"


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

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

CQueen::CQueen()
{
   iCount=0;
}

CQueen::~CQueen()
{

}

void CQueen::Output()
{
	
	
//	printf( "No.%-5d " , ++iCount);
	++iCount;
	for(int i=0;i<QUEENS;i++)
		backup[iCount-1][i] = Site[i];
//		memcpy(*backup[],Site,sizeof(int)*8);
/*
	for(i = 0 ; i < QUEENS ; i++)
		printf( "%d " , Site[i]);

	printf( "\n ");*/
}

//判断第n个皇后放上去之后，是否合法，即是否无冲突。
int CQueen::IsValid(int n)
{	
	for(int i=0;i<n;i++)
	{
		if(Site[i]==Site[n])//在同一列上
			return 0;
		
		if(abs(Site[i]-Site[n])==(n-i))//判断和前面的皇后有没有在意同一条对角线上
			return 0;
	}
	return 1;
}


//递归放置第n个皇后
void CQueen::Queen(int n)
{	
	if(n == QUEENS)
	{
		Output();	
		return;
	}
	
	for(int i=1; i<=QUEENS;i++)//i代表列 ,Site[n]代表第n+1个皇后在第n行的位置
	{
		Site[n] = i;
		if(IsValid(n))//每一列依次去查询  是否符合
			Queen(n + 1);
	}
}