8皇后问题.cpp

来自「代码质量不高」· C++ 代码 · 共 81 行

#include <iostream.h>
#include <math.h>
int x[100];       //表示皇后放的位置
int n;
int count;       //纪录打印的解个数
	

int  place(int k)
{
	//如果一个皇后能放在k行x[k]列，则返回true;否则返回false。x是一个
	//全程数组，进入此过程时已设置了k各值。
	int i;
	i=1;
	while (i<k)
	{
		if ((x[i]==x[k])||(abs(x[i]-x[k])==abs(i-k)))//在同一列或同一对角线上
			return 0;
		i=i+1;
	}
	return 1;
}

void print(int x[])
{
	cout<<"第"<<count<<"个解为："<<endl;
	for (int i=1;i<n;i++)
	{
		
		for (int j=1;j<x[i];j++)
			cout<<"*";
		cout<<"Q";
		for (int m=x[i]+1;m<=n;m++)
			cout<<"*";
		cout<<endl;
		
		//cout<<x[i]<<"   ";
	}
	
	cout<<endl;
}

void nqueens(int n)
{
	//此过程使用回溯算法求出一个在n*n棋盘上放置n个皇后，使其
	//不相互攻击的所有可能的位置
	int k;          //表示行
	x[1]=0;         
	k=1;            //k是当前的行；x[k]是当前列
	while (k>0)
	{
		x[k]=x[k]+1;   //移到下一列
	    while (x[k]<=n&&!place(k))   //在此处能否放置这个皇后
			x[k]=x[k]+1;
		if (x[k]<=n)
			if(k==n)
			{
				count++;
				print(x);
				
			}
			else
			{
				k=k+1;              //转向下一行
				x[k]=0;
				
			}
		else
			k=k-1;                  //回溯
	}

}


 
void main()
{
	n=8;
	count=0;
	nqueens(n);
	cout<<"解的个数为:"<<count<<endl;
}