n皇后问题.cpp

数值分析中的N皇后问题

// N皇后问题.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "math.h"
 

int judge(int *p, int j)	//判断当前棋子位置是否符合规则，是则返回1，否则返回0
{
	int i;
	for (i=0;i<j;i++)
	{
		if (p[j]==p[i])
			return 0;
		if (abs(p[j]-p[i])==j-i)
			return 0;
	}
	return 1;
}

int main() 
{ 
	cout << "  *******************************************" << endl;
	cout << "  **                                       **" << endl;
	cout << "  **             N 皇 后 问 题             **" << endl;
	cout << "  **                                       **" << endl;
	cout << "  *******************************************" << endl;

	int N;
	cout << "请输入皇后的个数：";
	cin >> N;

	int num=0;
	int *a;
	a=new int [N];		//a[i]表示第i行的后所在位置（a[3]=0表示第3行的后在第0列）
	int j;

	for (a[0]=0;a[0]<N;j=0,a[j]++)
	{
		int k=0;
		j=1;
		while (1)
		{
			int fl=0;
			for (a[j]=k;a[j]<N;a[j]++)
			{
				if (judge(a,j))
				{
					fl=1;
					j++;
					k=0;
					break;
				}
			}
			if (fl==0)
			{
				j--;
				k=a[j]+1;
			}
			if (j==N)
			{
				int m,n;
				for (m=0;m<N;m++)
				{
					for (n=0;n<N;n++)
						if (n==a[m])
							cout << "1  ";
						else
							cout << "0  ";
					cout << "\n";
				}
				cout << "\n";
				num++;
				j=j-2;
				k=a[j]+1;
			}
			if (j==0)
				break;
		}	
	}
	cout << "结果：在" << N << "×" << N << "的棋盘上，放置" << N << "个不能互相捕捉的“皇后”，共有" << num << "种布局。\n";

	return 0;

	delete [N] a;
}