nqueenproblem.cpp

来自「这是一个自己实现的N皇后问题c++解法」· C++ 代码 · 共 133 行

//行号和列号都是从0开始；
 
#include<iostream>
#include<math.h>
#include<iomanip>

using namespace std;

int position[1000];
bool isHappend[1000];
int n;
int count = 0;
bool isFirstAnswer = false;
bool last = false;

bool isPermit(int col, int row);
bool isNotSameCol(int col, int row);
bool isNotSameAng(int col, int row);
void print();
bool isCircle();


void main()
{
	cout << "请输入皇后数目！";
	cin >> n;
	int i;
	int row = 0;
	int flBack = 0;
	for(int j=0; j<=n-1; j++)
	{
		position[j] = -1;
	}
	while(true)
	{
		isHappend[position[0]] = true; 
		for(i=position[row]+1; i<=n-1; i++)
		{
			flBack = 0;
			if(isPermit(i, row))
			{
				position[row] = i;
				row++;
				break;
			}
		}
		if(i == n)
		{
			position[row] = -1;
			row--;
			if(position[row] == n - 1)
			{
				position[row] = -1;
				row--;
				while(position[row] == n - 1 && row != 0)
				{
					position[row] = -1;
					row--;
				}
			}
			flBack = 1;
		}

		if(isCircle())
			break;
		if(row == n)
		{
			count++;
			print();
			position[row-1] = -1;
			if(n <= 1)
				break;
			else
				row = n-2;
		}
	}
}

bool isPermit(int col, int row)
{
	if(isNotSameAng(col, row) && isNotSameCol(col,row))
		return true;
	else
		return false;
}

bool isNotSameCol(int col, int row)
{
	for(int i=0; i<=row-1; i++)
	{
		if(position[i] == col)
		{
			return false;
		}
	}
	return true;
}
bool isNotSameAng(int col, int row)
{
	for(int i=0; i<=row-1; i++)
	{
		if(abs(position[i] - col) == abs(i - row))
		{
			return false;
		}
	}
	return true;
}

void print()
{
	cout << count << endl;
	for(int i=0; i<=n-1; i++)
	{
		cout << '|';
		cout << setw(position[i] + 1) << setfill('.');
		cout << position[i];
		//cout << setw(0) << setfill(' ');
		cout << setw(n-position[i]) << setfill('.') << '|' << endl;
	}
	cout << endl;
}

bool isCircle()
{
	for(int i=0; i<=n-1; i++)
	{
		if(isHappend[i] == false)
			return false;
	}
	return true;
}