实现n皇后问题（回溯法）

 1 /*========================================
 2     功能：实现n皇后问题，这里实现4皇后问题
 3     算法：回溯法
 4 ==========================================*/
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 
 8 #define TRUE 1
 9 #define FALSE 0
10 #define NUM_QUEEN    4                    /* 皇后个数 */
11 
12 typedef int BOOL;
13 
14 void n_queen(int sol[], int n);
15 BOOL place(int solution[], int k);
16 void display();
17 
18 int solution[NUM_QUEEN + 1] = {0};            /* 皇后问题的解向量 */
19 
20 
21 void main()
22 {
23     n_queen(solution, NUM_QUEEN);
24     display();
25 }
26 /*=================================
27     功能：找出满足n皇后问题的解向量
28     输入：皇后个数n
29     输出：n皇后的解向量sol[]
30 ===================================*/
31 void n_queen(int sol[], int n)
32 {
33     int k = 1;                                    /* 从第一个皇后开始 */
34     sol[k] = 0;
35     while(k > 0)
36     {
37         sol[k] = sol[k] + 1;            
38         while(sol[k] <= n && !place(sol, k))    /* 如果sol[k]列不满足条件 找下一列 */
39             sol[k] = sol[k] + 1;
40         if(sol[k] <= n)                            /* 找到满足条件的列 */
41         {
42             if(k == n)
43                 break;                            /* 最后一个皇后处理完 直接退出 */
44             else
45                 k = k + 1;                        /* 处理下一个皇后 */
46         }
47         else                                    /* 判断完该行所有列 没有合适的位置 回溯 */
48         {
49             sol[k] = 0;
50             k = k - 1;
51         }
52     }
53 }
54 /*==========================================================
55     功能：判断第k个皇后的位置 是否正确 与前面k - 1个皇后比较
56     输入：前k - 1个解向量
57     输出：第k个位置是否正确
58 ============================================================*/
59 BOOL place(int sol[], int k)
60 {
61     int i;
62     
63     for(i = 1; i < k; i ++)
64     {
65         if(sol[i] == sol[k] || abs(sol[i] - sol[k]) == abs(i - k))
66             return FALSE;
67     }
68 
69     return TRUE;
70 }
71 /*===========================
72     功能：显示n皇后的解决向量
73     输入：无
74     输出：n皇后解决向量
75 =============================*/
76 void display()
77 {
78     int i = 1;
79     printf("%d QUEES solution:", NUM_QUEEN);
80     for(; i <= NUM_QUEEN; i ++)
81     {
82         printf("%d	", solution[i]);
83     }
84     printf("
");
85 }
n_queen