/*========================================

     功能：实现n皇后问题，这里实现4皇后问题

     算法：回溯法

 ==========================================*/

 #include <stdio.h>

 #include <stdlib.h>

 #define TRUE 1

 #define FALSE 0

 #define NUM_QUEEN    4                    /* 皇后个数 */

 typedef int BOOL;

 void n_queen(int sol[], int n);

 BOOL place(int solution[], int k);

 void display();

 int solution[NUM_QUEEN + ] = {};            /* 皇后问题的解向量 */

 void main()

 {

     n_queen(solution, NUM_QUEEN);

     display();

 }

 /*=================================

     功能：找出满足n皇后问题的解向量

     输入：皇后个数n

     输出：n皇后的解向量sol[]

 ===================================*/

 void n_queen(int sol[], int n)

 {

     int k = ;                                    /* 从第一个皇后开始 */

     sol[k] = ;

     while(k > )

     {

         sol[k] = sol[k] + ;

         while(sol[k] <= n && !place(sol, k))    /* 如果sol[k]列不满足条件 找下一列 */

             sol[k] = sol[k] + ;

         if(sol[k] <= n)                            /* 找到满足条件的列 */

         {

             if(k == n)

                 break;                            /* 最后一个皇后处理完 直接退出 */

             else

                 k = k + ;                        /* 处理下一个皇后 */

         }

         else                                    /* 判断完该行所有列 没有合适的位置 回溯 */

         {

             sol[k] = ;

             k = k - ;

         }

     }

 }

 /*==========================================================

     功能：判断第k个皇后的位置 是否正确 与前面k - 1个皇后比较

     输入：前k - 1个解向量

     输出：第k个位置是否正确

 ============================================================*/

 BOOL place(int sol[], int k)

 {

     int i;

     for(i = ; i < k; i ++)

     {

         if(sol[i] == sol[k] || abs(sol[i] - sol[k]) == abs(i - k))

             return FALSE;

     }

     return TRUE;

 }

 /*===========================

     功能：显示n皇后的解决向量

     输入：无

     输出：n皇后解决向量

 =============================*/

 void display()

 {

     int i = ;

     printf("%d QUEES solution:", NUM_QUEEN);

     for(; i <= NUM_QUEEN; i ++)

     {

         printf("%d\t", solution[i]);

     }

     printf("\n");

 }