构造.cpp

八皇后问题全解 有回溯法（函数

//构造原理
/*
一、当n mod 6 != 2 且 n mod 6 != 3时，有一个解为：
2,4,6,8,...,n,1,3,5,7,...,n-1       (n为偶数)
2,4,6,8,...,n-1,1,3,5,7,...,n       (n为奇数)

(上面序列第i个数为ai，表示在第i行ai列放一个皇后；... 省略的序列中，相邻两数以2递增。下同)

二、当n mod 6 == 2 或 n mod 6 == 3时，
(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)

k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1         (k为偶数,n为偶数)
k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n       (k为偶数,n为奇数)

k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1               (k为奇数,n为偶数)
k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n           (k为奇数,n为奇数)

*/

#include <iostream>
#include <vector>
using namespace std;

void NQueen(int *Queen,int n)
{
	int mod = n%6;
	int div = n%2;
	int i = 0,j = 0,k = 0;
	
	if(mod != 2 && mod != 3)
	{
		if( div == 0)
		{
			for(i = 0,j = 2; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if( j == n)
				{
					j = 1-2;
				}
			}

		}
		else
		{
			for(i = 0,j = 2; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if( j == n-1)
				{
					j = 1-2;
				}
			}
		}
	}
	else//当n mod 6 == 2 或 n mod 6 == 3时
	{
		if(div == 0)//n为偶数
		{
			k = n/2;
		}
		else        //n为奇数
		{
			k = (n-1)/2;
		}
		int kk = k%2;
		//k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1(k为偶数,n为偶数)
		if(div == 0 && kk == 0)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n)
				{
					j = 2-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n-1)
				{
					j = 1-2;
				}

			}
		}
		//k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n(k为偶数,n为奇数)
		if(kk == 0 && div != 0)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n-1)
				{
					j = 2-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n-2)
				{
					j = 1-2;
				}
				else if(j == k+1)
				{
					j = n - 2;
				}
					 
			}

		}
		//k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1(k为奇数,n为偶数)
		if(kk != 0 && div == 0)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n-1)
				{
					j = 1-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n)
				{
					j = 2-2;
				}
			}
		}
		//k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n(k为奇数,n为奇数)
		if(kk == 1 && div == 1)
		{
			for(i = 0,j = k; i < n; i++,j+=2)
			{
				Queen[i] = j;
				if(j == n-2)
				{
					j = 1-2;
				}
				else if(j == k-2)
				{
					j = k+3-2;
				}
				else if(j == n-1)
				{
					j = 2-2;
				}
				else if(j == k+1)
				{
					j = n-2;
				}
			}

		}
	}


}

void Print(int *Queen,int n)
{
	for(int  i = 0; i < n; i++)
	{
		cout<<Queen[i]<<' ';
	}
	cout<<'\n';
}

bool Check(int *Queen,int n)
{
	int i = 0,j = 0;
	int wrong = 0;
	for(i = 0; i < n; i++)
	{
		for(j = i+1; j < n; j++)
		{
			if(Queen[i] == Queen[j] || Queen[i]-i == Queen[j]-j || Queen[i]+i == Queen[j]+j )
			{
				wrong++;
			}
		}
	}
	cout<<"wrong="<<wrong<<endl;
	if(wrong == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void main()
{
	int n = 0;
	int *Queen;
	do
	{
	cout<<"请输入皇后的个数：";
	cin>>n;
	Queen =  new int[n];
	for(int i = 0; i < n; i++)
	{
		Queen[i] = 0;
		cout<<"i = "<<i <<endl;
	}
	cout<<"i = "<<i <<endl;
	NQueen(Queen,n);
	Check(Queen,n);
	Print(Queen,n);
	delete Queen;
	}while(n > 4);

}