queenmain.cpp

递归方法解决N皇后问题

//////////////////////////////////////////////////////////////////////////
//说明：本程序用递归方法解决N皇后问题
//
//////////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#define N 8

void Trial(int nNowRow, int nChess[]);
void Output(const int nChess[]);
bool IsChessOK(int nNowRow, const int nChess[]);

void main(void)
{
	int nChess[N + 1] = {0};//棋盘标记，记录每一行落子的所在列，nChess[0]未使用
	Trial(1, nChess);
	system("pause");
}

//行棋函数
void Trial(int nNowRow, int nChess[])
{
	if (nNowRow > N)
	{
		Output(nChess);//输出当前棋盘
	}
	else
	{
		for (int nList = 1; nList <= N; nList++)
		{	
			nChess[nNowRow] = nList;//放置棋子
			if (IsChessOK(nNowRow, nChess))//当前布局合法
			{
				Trial(nNowRow + 1, nChess);//走下一步
			}
			else
			{
				nChess[nNowRow] = 0;//移除棋子
			}
		}
	}
}

//输出棋盘
void Output(const int nChess[])
{
	for (int i = 1; i <= N; i++)
	{
		cout << nChess[i] << " ";
	}
	cout << endl;
}

//检查棋盘布局是否合法
//已经下的棋盘中不能有在同一列,同一对角线的
bool IsChessOK(int nNowRow, const int nChess[])
{
	int nTemp;
	for (int i = 1; i <= nNowRow; i++)
	{
		nTemp = nChess[i];
		for (int j = i + 1; j <= nNowRow; j++)
		{
			if (nTemp == nChess[j] + j - i || nTemp == nChess[j] - j + i)//如果在同一对角线返回错误
			{
				return false;
			}
			if (nTemp == nChess[j])//如果在同一列返回错误
			{
				return false;
			}
		}
	}
	return true;
}