queen.cpp

解决八皇后问题的算法

#include<iostream>
#include<string>
#include<stack>
using namespace std;

const int n=8;

typedef struct {
	int p[n];
	int k;
	int mark;
}node;

int total;

void print(const node& res)
{
	bool f[n][n];
	memset(f,0,sizeof(f));
	for (int i=0; i<n; i++)
		f[res.p[i]][i]=1;
	total++;
	if (total<10) cout<<"The 00"<<total<<" scheme"<<endl;
	else if (total<100) cout<<"The 0"<<total<<" scheme"<<endl;
	else if (total<1000) cout<<"The "<<total<<" scheme"<<endl;
	for (i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
			if (!f[i][j]) cout<<'*'<<' ';
			else cout<<'@'<<' ';
		cout<<endl;
	}
}

bool check(const node& res,int k)
{
	int row=res.k+1;
	for (int i=0; i<n; i++)
		if (i!=k)
		{
			if (res.p[i]!=-1 && abs(row-res.p[i])==abs(k-i))
				return false;
		}
	return true;
}

int main(){
	
	total=0;
	stack<node> s;
	for (int i=0; i<n; i++)
	{
		node tmp;
		tmp.k=0;
		for (int j=0; j<n; j++) tmp.p[j]=-1;
		tmp.p[i]=0; tmp.mark=0;
		s.push(tmp);
		while (!s.empty())
		{
			node t=s.top();
			if (t.mark==1) {
				s.pop();
				continue;
			}
			s.top().mark=1;
			if (t.k==n-1) {
				print(t);
				s.pop();
				continue;
			}
			bool ok=false;
			for (int j=0; j<n; j++)
				if (t.p[j]==-1 && check(t,j))
				{
					node newnode;
					newnode.k=t.k+1;
					for (int x=0; x<n; x++) newnode.p[x]=t.p[x];
					newnode.p[j]=newnode.k;
					newnode.mark=0;
					s.push(newnode);
					ok=true;
				}
			if (!ok) s.pop();
		}
	}
	return 0;
}