queen.cpp

C++Example实用的算法:包括枚举

//回溯法
//八皇后问题
#include <iostream.h>

#define QUEEN 8      //定义棋盘的大小

int* Q = new int[QUEEN];       //生成数组存储各行状态

//符合（不冲突），函数返回true
//不符合（冲突），函数返回false
bool Check(int* Q , int row){
	for(int i = 0 ; i < row ; i++ ){
		if( Q[i] == Q[row] || (i-row) == (Q[i]-Q[row]) || (i-row) == (Q[row]-Q[i]) )
			return false;
	}
	return true;
};

int main()
{
	int num = 0;             //存储符合条件的总数
	bool nextRow = false;    //标记是否进行下一行测试
	bool nextLine = true;    //标记是否进行下一列测试
	for( int i = 0 ; i < QUEEN ; i++ )
		Q[i] = -1;
	for( int row = 0 ; row < QUEEN ; row++ ){
		for( int line = Q[row] + 1; line < QUEEN && nextLine; line++ ){
			Q[row] = line;
			//判断是否符合，不符合（即冲突）则Check返回false
			//符合（不冲突），则进入此 if 语句
			if( Check(Q,row) ){
				nextLine = false;
				nextRow = true;
			}
			else if( line == QUEEN-1 ){
				nextRow = false;
			}
		}
		if( row == QUEEN - 1 && nextRow ){
			num++;
			nextRow = false;
		}
		if( ! nextRow ){
			if( row == 0 )
				break;
			Q[row] = -1;
			row -= 2;         //回退两行
		}
		nextLine = true;
	}
	cout<<num<<endl;
	return 0;
}