queen.cpp

用概率算法结合回溯思想实现n皇后问题

// Queen.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "queen.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int uniform(int a,int b)
{
	int random = rand() % b + 1;
	return random;
}

bool Security(int i,int j)
{
	bool ret=true;
	
	for(int raw=1; raw < i; raw++)
	{ //行号
		if(	j == queenCol[raw] ||
			j-queenCol[raw] == raw-i ||
			j-queenCol[raw] == i-raw)
		{ //冲突
			ret = false;
			break;
		}
	}
	
	return ret;
}


bool Backtrace(int k,int n,int start,int stepVegas)
{ //对后几行回溯搜索
	if(k > n)  return true;
	if(start > n && k == stepVegas+1) return false;

	int i;
	i = start;

	while( i <= n )
	{
		if( Security(k,i) ) break;
		i++;
	}

	printf("%d,",k);
	if( i <= n )
	{ //found
		queenCol[k] = i;
		return Backtrace(k+1,n,1,stepVegas);
	}
	else
	{ // not found any col int current raw
		if( k == stepVegas+1) return false;	
		return  Backtrace(k-1,n,queenCol[k-1]+1,stepVegas);
	}
}


bool QueenLV(int n,int stepVegas)
{
	int nb = 1;
	int i,j;

	for(i=1; i <=n; i++)
	{
		queenCol[i] = 0;
	}

	int k = 0; // 行号

	if( k < stepVegas )
	{
		k = 1;
		do
		{
			nb = 0;
			for(i=1; i <= n; i++)
			{ //列号
				if(Security(k,i))
				{ // 安全列
					nb++;
					if(uniform(1,nb) == 1)
					{
						j = i;
					}
				}
			}//end for
			if(nb > 0)
			{
				queenCol[k] = j;
				k++;
			}
		}while( nb > 0 && k < stepVegas);	
	} //end if

	printf("end LV %d\n",k);

	if( nb > 0)
	{
		return Backtrace(k,n,1,stepVegas);
	}
	else
	{
		return false;
	}

}


int _tmain(int argc, _TCHAR* argv[])
{
	int i;
	bool ifSucc;

	srand((unsigned)time(NULL));

	while(true){
		
		ifSucc = true;
		QueenLV(N,8);  //有时末尾几个为0；LV算法不成功的概率

//		printf("out\n");

		for(i=1; i<=N; i++)
		{
			if(queenCol[i] == 0)
			{
				ifSucc = false;
				break;
			}
		}
		if( ifSucc == true) break;
	}
//-------------------------------------------
//print	
	int print[N+1][N+1];

	for(i=1; i<=N; i++)
	{
		for(int j=1; j <= N; j++ ){
			print[i][j] = '-';
		}
	}

	for(i=1; i <= N; i++)
	{
		print[i][queenCol[i]] = 'X';
	}

	for(i=1; i<=N; i++)
	{
		for(int j=1; j <= N; j++ )
		{
			printf(" "); 
			printf("%c",print[i][j]);
		}
		printf("\n");
	}

	return 0;
}