转载请注明出处：http://blog.csdn.net/ns_code/article/details/26614999

剑指offer上解决八皇后问题，没实用传统的递归或非递归回溯法，而是用了非常巧妙的全排列法。

先说下八皇后问题：在8 X 8的国际象棋上摆放八个皇后，使其不能相互攻击，即随意两个皇后不得处于同一行，同一列或者允许对角线上，求出全部符合条件的摆法。

全排列解决八皇后问题的思路例如以下：

因为8个皇后不能处在同一行，那么肯定每一个皇后占领一行，这样能够定义一个数组A[8]，数组中第i个数字，即A[i]表示位于第i行的皇后的列号。先把数组A[8]分别用0-7初始化，接下来对该数组做全排列，因为我们用0-7这7个不同的数字初始化数组，因此随意两个皇后肯定也不同列，那么我们仅仅须要推断每一个排列相应的8个皇后中是否有随意两个在同一对角线上就可以，即对于数组的两个下标i和j，假设i-j==A[i]-A[j]或i-j==A[j]-A[i]，则觉得有两个元素位于了同一个对角线上，则该排列不符合条件。

代码例如以下：

#include<stdio.h>

void swap(int *a,int *b)

{

	int temp = *a;

	*a = *b;

	*b = temp;

}

/*

假设有符合条件的摆法，打印出全部的摆法，否则，什么也不打印

*/

void CubVertex(int *A,int len,int begin)

{

	if(A==NULL || len!=8)

		return;

	if(begin == len-1)

	{

		int i,j;

		bool can = true;	//是否又符合条件的摆法

		for(i=0;i<len;i++)

			for(j=i+1;j<len;j++)

				if(i-j==A[i]-A[j] || i-j==A[j]-A[i])

				{

					//假设随意两个在一条对角线上，则不符合

					can = false;

					break;

				}

		//有符合的摆法，就打印出来

		if(can)

		{

			for(i=0;i<len;i++)

				printf("%d ",A[i]);

			printf("\n");

		}

	}

	else

	{

		int i;

		for(i=begin;i<len;i++)

		{

			swap(&A[begin],&A[i]);

			CubVertex(A,len,begin+1);

			swap(&A[begin],&A[i]);

		}

	}

}

int main()

{

	int A[8] = {0,1,2,3,4,5,6,7};

	CubVertex(A,8,0);

	return 0;

}

測试结果：

四皇后：

四皇后总共同拥有2中摆法。

1、3、0、2的意思是指：第0行上的皇后摆放在第1个位置（从0開始），第1行上的皇后摆放在第3个位置，第3行上的皇后摆放在第0个位置，第4行上的皇后摆放在第2个位置。

八皇后：

八皇后总共同拥有92种摆法。