queen_means.cpp

n皇后问题的进阶解法

#include "stdafx.h"
#include"Queen_Means.h"
#include<iostream>
using namespace std;
void Backward(Position & p,const int Size)
{
	if(p.y<Size-1)
		p.y++;
}
bool Adjust(const Position p1,Position& p2,const int Size)
{
	 while((p1.x==p2.x)||(p1.y==p2.y)||(p1.x+p1.y==p2.x+p2.y)||(p1.x-p1.y==p2.x-p2.y))
	 {
	   if(p2.y==Size-1)break;
	   Backward(p2,Size);
	 }
	if((p1.x==p2.x)||(p1.y==p2.y)||(p1.x+p1.y==p2.x+p2.y)||(p1.x-p1.y==p2.x-p2.y))return false;
	else return true;
}
void Queen_Arrange(Position* p,const int Size)
{
	int i,j;
	for(i=0;i<Size;i++)
	{
		p[i].x=i;
		p[i].y=0;
	}
	for(i=1;i<Size;)
		for(j=0;j<i;)
		{
			if(Adjust(p[j],p[i],Size))
			{
				j++;
			}
			else
			{
				Backward(p[0],Size);
				for(int k=1;k<i;k++)
				p[k].y=0;
				i=1;
				break;
			}
			if(i==j)
			{
				i++;
				break;
			}
		}
}