【剑指offer】八皇后问题

转载请注明出处：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]，则认为有两个元素位于了同一个对角线上，则该排列不符合条件。

    代码如下：

[cpp] view plaincopy

1. #include<stdio.h>
3. void swap(int *a,int *b)  
4. {  
5. int temp = *a;  
6.     *a = *b;  
7.     *b = temp;  
8. }  
10. /*
11. 如果有符合条件的摆法，打印出所有的摆法，否则，什么也不打印
12. */
13. void CubVertex(int *A,int len,int begin)  
14. {  
15. if(A==NULL || len!=8)  
16. return;  
18. if(begin == len-1)  
19.     {  
20. int i,j;  
21. bool can = true;    //是否又符合条件的摆法
22. for(i=0;i<len;i++)  
23. for(j=i+1;j<len;j++)  
24. if(i-j==A[i]-A[j] || i-j==A[j]-A[i])  
25.                 {  
26. //如果任意两个在一条对角线上，则不符合
27.                     can = false;  
28. break;  
29.                 }  
30. //有符合的摆法，就打印出来
31. if(can)  
32.         {  
33. for(i=0;i<len;i++)  
34.                 printf("%d ",A[i]);  
35.             printf("\n");  
36.         }  
37.     }  
38. else
39.     {  
40. int i;  
41. for(i=begin;i<len;i++)  
42.         {  
43.             swap(&A[begin],&A[i]);  
44.             CubVertex(A,len,begin+1);  
45.             swap(&A[begin],&A[i]);  
46.         }  
47.     }  
48. }  
50. int main()  
51. {  
52. int A[8] = {0,1,2,3,4,5,6,7};  
53.     CubVertex(A,8,0);  
54. return 0;  
55. }  

    测试结果：

    四皇后：

    四皇后总共有2中摆法。

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

    八皇后：

    八皇后总共有92种摆法。