八皇后问题 回溯法.txt

NUAA ACM OJ源码

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <time.h>
using namespace std;

#define START 1
#define MAX 30

//八皇后问题 回溯法
/*
输入
4

输出
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
*/
int where[MAX]={0};//初始化，未开始访问

bool isok(int now)
{
	int i;
	for(i=1;i<now;i++)
		if((where[i]-where[now])==(i-now)||where[i]==where[now]) return false;
	return true;
}

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			if(where[i]==j) cout<<"1 ";
			else cout<<"0 ";
		cout<<endl;
	}
	cout<<endl;
//	system("pause");
}
bool Queue(int num)
{
/*
	回溯法的整体思路：
	次数=1；初始化所有状态x[次数]为0（1<=x[次数]<=限制）
	while(次数〉=1）
	{
		x[次数]++；
		while(x[次数]<=限制）
		{
			if(x[次数]符合条件) break;
			else x[次数]++；
		} 
		if(x[次数]<=限制)
		{
			if(次数==总次数) return true;
			else 次数++;
		}
		else
		{
			x[次数]=0；
			次数--；
		}
	}
	return false;
*/
	int k=1;
	while(k>=1)
	{
		where[k]++;//访问第k行的下一个位置
		while(where[k]<=num)
		{
			if(isok(k)) break;
			else where[k]++;//这一位置不符合条件，访问下一个位置
		}
		if(where[k]<=num) 
		{	//在第k行找到了符合条件的位置
			if(k==num) 
			{	//找到所有位置
				return true;
			}
			else k++;//找到部分位置，进行对k+1行的访问
		}
		else 
		{	//回溯
			where[k]=0;//将当前点的访问位置置为初始化
			k--;
		}
//		print(num);
	}
	return false;
}

int main()
{
	int num,timea,timeb;
	cout<<"输入棋盘大小:";
	cin>>num;
	timea=time(NULL);
	if(Queue(num)) print(num);
	else cout<<"没有解决方案"<<endl;
	timeb=time(NULL);
	cout<<"所花时间为"<<timeb-timea<<"s"<<endl;
	return 0;
}