n皇后问题队列分支限界法

N皇后问题解法，采用队列分支限界算法。c++编程。

#include 
#include 
using namespace std;

void NQueens（）;
bool CanPos（int *pos int level int i）;
int * GetNQueensPos（int n）;

void main（）
{
	NQueens（）;
}

int * GetNQueensPos（int n）
{
	int *pos = new int[n];
	int level = 0;
	queue *QPos = new queue（）;
	queue *QLevel = new queue（）;

	while （true）
	{
		if （level == n）	
		{
			break;
		}
		for （int i = 1; i <= n; ++i）
		{
			if （CanPos（pos level i））
			{
				pos[level] = i;
				QPos->push（pos）;
				QLevel->push（level + 1）;
				break;
			}
		}
		pos = QPos->front（）;
		QPos->pop（）;
		level = QLevel->front（）;
		QLevel->pop（）;
	}

	return pos;
}

bool CanPos（int *pos int level int i）
{
	for （int j = 0; j < level; ++j）
	{
		if （abs（pos[j] - i） == abs（j - level） || （pos[j] == i））
		{
			return false;
		}
	}
	return true;
}

void NQueens（）
{
	FILE *file;

	if （（file = fopen（“input.txt“ “r“）） == NULL）
	{
		cout << “Couldn‘t find the file ‘input.txt‘!“ << endl;
	}
	else
	{
		int n;
		fscanf （file “%d“ &n）;
		fclose（file）;

		if （（file = fopen（“output.txt“ “w“）） == NULL）
		{
			cout << “Couldn‘t create the file ‘output.txt‘!“ << endl;
		}
		else
		{
			int *pos = GetNQueensPos（n）;
			cout << n << endl;
			for （int i = 0; i < n; ++i）
			{
				fprintf （file “%d “ pos[i]）;
				cout << pos[i] << “ “;
			}
			cout << endl;
			fclose（file）;
		}
	}
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1442  2008-12-04 14:45  n皇后问题\n皇后问题.cpp

     文件         10  2008-12-17 20:34  n皇后问题\output.txt

     文件          1  2008-12-04 14:45  n皇后问题\input.txt

     目录          0  2008-12-09 12:22  n皇后问题

----------- ---------  ---------- -----  ----

                 1453                    4