八皇后問題


    在一個8×8國際象棋盤上，有8個皇后，每個皇后占一格；

要求皇后間不會出現相互“攻擊”的現象，即不能有兩個皇后處在同一行、同一列或同一對角線上。

    采用一維數組來進行處理。數組的下標i表示棋盤上的第i列，a[i]的值表示皇后在第i列所放的位置。

如：a[1]=5，表示在棋盤的第一例的第五行放一個皇后。

   程序中首先假定a[1]=1，表示第一個皇后放在棋盤的第一列的第一行的位置上，

然后試探第二列中皇后可能的位置，找到合適的位置后，再處理后續的各列，

這樣通過各列的反復試探，可以最終找出皇后的全部擺放方法。

#include<stdio.h>
#define NUM 8     /*定義數組的大小*/
int a[NUM+1];
void main()
{
   int i,k,flag,not_finish=1,count=0;
   i=1;          /*正在處理的元素下標，表示前i-1個元素已符合要求，正在處理第i個元素*/
   a[1]=1;        /*為數組的第一個元素賦初值*/
   printf("The possible configuration of 8 queens are:\n");
   while(not_finish)                 /*not_finish=1:處理尚未結束*/
   {
      while(not_finish&&i<=NUM)      /*處理尚未結束且還沒處理到第NUM個元素*/
      {
         for(flag=1,k=1;flag&&k<i;k++)     /*判斷是否有多個皇后在同一行*/
            if(a[k]==a[i])flag=0;
         for(k=1;flag&&k<i;k++)      /*判斷是否有多個皇后在同一對角線*/
            if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
               if(!flag)     /*若存在矛盾不滿足要求，需要重新設置第i個元素*/
               {
                  if(a[i]==a[i-1])        /*若a[i]的值已經經過一圈追上a[i-1]的值*/
                  {
                  i--;          /*退回一步，重新試探處理前一個元素*/
                  if(i>1&&a[i]==NUM)
                     a[i]=1;           /*當a[i]為NUM時將a[i]的值置1*/
                  else if(i==1&&a[i]==NUM)
                     not_finish=0;         /*當第一位的值達到NUM時結束*/
                  else a[i]++;           /*將a[i]的值取下一個值*/
               }
               else if(a[i]==NUM) a[i]=1;
               else a[i]++;         /*將a[i]的值取下一個值*/
            }
            else if(++i<=NUM)
               if(a[i-1]==NUM) a[i]=1;   /*若前一個元素的值為NUM則a[i]=1*/
               else a[i]=a[i-1]+1;        /*否則元素的值為前一個元素的下一個值*/
         }
         if(not_finish)
         {
            ++count;
            printf((count-1)%3?" [%2d]: ":" \n[%2d]: ",count);
            for(k=1;k<=NUM;k++)          /*輸出結果*/
               printf(" %d",a[k]);
            if(a[NUM-1]<NUM) a[NUM-1]++;     /*修改倒數第二位的值*/
            else a[NUM-1]=1;
            i=NUM-1;               /*開始尋找下一個足條件的解*/
         }
      }
}
*運行結果