随机+回溯求八皇后.txt

自己编写的八皇后问题的各种随机算法：包括了随机算法

#include <iostream>
#include <set>
#include <ctime>
using namespace std;
const int N = 100;
int x[N];
int ok[N];
int result[14] = {0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712};

double Randomf0_1()         //产生0-1之间的浮点数
{
	return ((rand()%1000)*0.001);
}

int Randomf(int a,int b)   //产生a-b之间的整数
{
	return a + (b - a + 1) * Randomf0_1();
}

bool Place(int k)
{
	for(int j = 1; j <= k-1; j++){
		if((abs(k-j) == abs(x[j]-x[k]))||(x[j] == x[k]))
			return false;
	}
	return true;
}

bool QueensTract(int begin,int n)          //回溯法得出问题所有解
{
	int k,i;
	x[begin] = 0;
	k = begin;
	while(k > begin - 1 ){
		x[k]++;
		while((x[k] <= n) && !Place(k)){
			x[k]++;
		}
		if(x[k] <= n)
			if(k == n){				
				return true;
			}
			else
			{
				k++;
				x[k] = 0;
			}
			else 
				k--;
	}
	return false;
}


bool QueensLVB(int x[],int n,int stopFlag)
{
	int k = 0;
	int count;
	int i;
	while(k < stopFlag){
		count = 0;
		for(i = 1; i <= n; i++){
			x[k+1] = i;
			if(Place(k+1)){ // 放置在某一行中所有可行的位置，然后随机抽取
				count = count + 1;
				ok[count] = i;
			}
		}
		if(count == 0)
			return false;
		i = ok[Randomf(1,count)];  // 随机抽取在该行可行的位置
		k = k+1;
		x[k] = i;
	}
	return QueensTract(stopFlag+1,n);
}

int main()
{
	int n;
	scanf("%d",&n);
	if(n == 2 || n == 3){
		printf("%d\n",0);
		return 0;
	}
	srand((unsigned)time(NULL));  //注意srand一般不要放在循环里面，否则会导致错误
	int tmp = 0;
	int num = 0;
	set<int> mySet;
	while(true){
		if(QueensLVB(x,n,n/2)){
			printf("%d\n",result[n]);
			for(int i = 1; i <= n; i++)
				printf("%d %d\n",i,x[i]);
			break;
		}
	}
	return 0;
}