main.cpp

自己写的四皇后问题的算法

//============================================================
//工程名称：四皇后问题的回朔算法
//实现功能：在在四格对称棋盘中找出4皇后的位置所在
//包含文件：main.h
//完成人：刘刚
//完成时间：2006/7/24
//============================================================
/*
算法分析：数组a、b、c分别用来标记冲突，a数组代表行冲突，从a[0]~a[3]
代表第1行到第4行，如果某列上已经有皇后，则为1，否则为0；
 数组b代表主对角线冲突，为b[i_row+i_line]，即从b[0]~b[6]，
 如果某条主对角线上已经有皇后，则为1，否则为0；
 数组c代表从对角线冲突，为c[i_line-i_row+3]，即从c[0]~c[6]，
 如果某条从对角线上已经有皇后，则为1，否则为0；
*/

#include <iostream>
using namespace std;

//*******************************************************
//函数名：bool four_queens(int row[4])
//参数：输入参数大小为4数组
//返回值：如果有解为真，无解为假
//(如果有解,则第k个皇后的位置在第k列,第row[k]行) 
//*******************************************************
bool four_queens(int row[4])
{
	int k=0;   //从第一列开始
	int a[4];  //用于标记行冲突
	int b[7];  //用于标记主对角线冲突 
	int c[7];  //用于标记从对角线冲突
	int i_line;  //定义列编号
	int i_row;   //定义行编号

	row[0]=0;
	for(int i=0;i<4;i++)
		a[i]=0;
	for(i=0;i<7;i++)
	{
		b[i]=0;
		c[i]=0;
	}                //初始化

	while(k>=0)
	{
		row[k]=row[k]+1;  //k+1列中一个合法的移动
		while(row[k]<=4)
		{
			i_line=k;
			i_row=row[k]-1;
			if(a[i_row]==0&&b[i_row+i_line]==0&&c[i_line-i_row+3]==0)
			{
				a[i_row]=1;//标记下一次该行上不能放皇后
				b[i_row+i_line]=1;//标记下一次主对角线不能放皇后
				c[i_line-i_row+3]=1;//标记下一次从对角线不能放皇后
				break;
			}
			else
				row[k]=row[k]+1;
		}
		if(row[k]<=4)
			if(k==3)
				return true;
			else
			{
				k=k+1;
				row[k]=0;
			}
		else
		{
			k=k-1;
			i_line=k;
			i_row=row[k]-1;   
			a[i_row]=0;//标记上一次该行上不能放皇后清零 
			b[i_row+i_line]=0;//标记上一次主对角线不能放皇后清零
			c[i_line-i_row+3]=0;//标记上一次从对角线不能放皇后清零
			
		}
	}
	return false;
}
//----------------------------------------end--------------------------------

//********************************************************************************
//主函数main()完成4皇后算法的测试功能
//********************************************************************************
void main()
{
	int row[4];
	for(int i=0;i<4;i++)
		row[i]=0;
	if(four_queens(row))
		for(i=0;i<4;i++)
			cout<<row[i]<<" "<<endl;
	else
		cout<<"error!";
}