queens.cpp

我们采用最小冲突启发式修补算法来求N皇后的解

//采用启发式修补解N皇后问题

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

void shuffle(int Queen[],const int n)
{//随机取得各行的初始皇后位置，以Queen[i]表示第i行的皇后位置
	for(int i=0;i<n;i++)
		Queen[i]=abs(rand())%n;
}
int collision(int Queen[],const int row,const int column,const int n)
{  //计算每个位置的冲突值
	int bug=0;
	for(int i=0;i<n;i++)
	{
		if ((i!=row)&&(Queen[i]==column||(Queen[i]-column)==(i-row)
			||(Queen[i]-column)==(row-i)))//同列，同对角线的情况
            bug++;
	}
	return bug;
}

void show(int Queen[],const int n)
{//打印皇后图
	
	cout<<"╭";
	for(int k=0;k<n-1;k++)
		cout<<"─┬";
	cout<<"─╮"<<endl;
    for(int i=0;i<n-1;i++)
	{ 
		cout<<"│";
	  for(int j=0;j<n;j++) 
	      cout<<((j==Queen[i])? "凤" :"  ")<<"│";//有皇后的位置用"凤"
       cout<<endl;
	   cout<<"├";
	  for(j=0;j<n-1;j++)
	      cout<<"─┼";
	   cout<<"─┤"<<endl;    
	 }
	  cout<<"│";
	  for(int j=0;j<n;j++) 
	      cout<<((j==Queen[n-1])? "凤" :"  ")<<"│";//有皇后的位置用，没有的用_
       cout<<endl;
    cout<<"╰";
	for(k=0;k<n-1;k++)
		cout<<"─┴";
	cout<<"─╯"<<endl; 
 cout<<endl;
}
	
int repair(int Queen[],const int n)
{ //启发式修补  
	int max=-1;//标志行行之间冲突数
	int minbug=n;
	int count=0;
	while(max!=0&&count<=100)
	{   
		max=0;
		for(int i=0;i<n;i++)
		{   
			minbug=collision(Queen,i,Queen[i],n);//取得当前的冲突数，不断优化
			int temp=Queen[i];
			for(int j=0;j<n;j++)
			{
				int bug=collision(Queen,i,j,n);
				if(bug<=minbug&&j!=temp)
				{ //保持皇后在等冲突的情况下不断变更位置，有利于后面行的优化
				  minbug=bug;
				  Queen[i]=j;
				}
			}
			if (minbug>max)
				max=minbug;
		}
		show(Queen,n);
		count++;
	}

	return count;
}


void main()
{   
	int n=-1;
	int step=0;
	cout<<"Welcome to N Queen Settlement"<<endl;
	cout<<"Input N (you would better input a interge minor to 15):"<<endl;
	cin>>n;
	if(n<=0)
	{
		cout<<"Illegal Input!"<<endl;
        return;
	}
	int* Queen=new int[n];
	srand(time(NULL));//取得随机种子
	shuffle(Queen,n);
	cout<<"The oringinal state:"<<endl;
    show(Queen,n);
	step=repair(Queen,n);
	if(step>100)
	{
		cout<<"Could find solution within 100 steps,Try again!"<<endl;
	    return;
	}
    cout<<"After "<<step+1<<" steps"<<endl;
    cout<<"The goal state arrives!"<<endl;
}