C趣味編程百例(32)八皇后問(wèn)題

98. 八皇后問(wèn)題
     在一個(gè)8×8國(guó)際象棋盤(pán)上，有8個(gè)皇后，每個(gè)皇后占一格；要求皇后間不會(huì)出現(xiàn)相互“攻擊”的現(xiàn)象，即不能有兩個(gè)皇后處在同一行、同一列或同一對(duì)角線上。問(wèn)共有多少種不同的方法。
    *問(wèn)題分析與算法設(shè)計(jì)
     這是一個(gè)古老的具有代表性的問(wèn)題，用計(jì)算機(jī)求解時(shí)的算法也很多，這里僅介紹一種。
     采用一維數(shù)組來(lái)進(jìn)行處理。數(shù)組的下標(biāo)i表示棋盤(pán)上的第i列，a[i]的值表示皇后在第i列所放的位置。如：a[1]=5，表示在棋盤(pán)的第一例的第五行放一個(gè)皇后。
     程序中首先假定a[1]=1，表示第一個(gè)皇后放在棋盤(pán)的第一列的第一行的位置上，然后試探第二列中皇后可能的位置，找到合適的位置后，再處理后續(xù)的各列，這樣通過(guò)各列的反復(fù)試探，可以最終找出皇后的全部擺放方法。
     程序采用回溯法，算法的細(xì)節(jié)參看程序。
    *程序與程序注釋
    #include
    #define NUM 8 /*定義數(shù)組的大小*/
    int a[NUM+1];
    void main()
    {
     int i,k,flag,not_finish=1,count=0;
     i=1; /*正在處理的元素下標(biāo)，表示前i-1個(gè)元素已符合要求，正在處理第i個(gè)元素*/
     a[1]=1; /*為數(shù)組的第一個(gè)元素賦初值*/
     printf("The possible configuration of 8 queens are:\n");
     while(not_finish) /*not_finish=1:處理尚未結(jié)束*/
     {
     while(not_finish&&i<=NUM) /*處理尚未結(jié)束且還沒(méi)處理到第NUM個(gè)元素*/
     {
     for(flag=1,k=1;flag&&k     if(a[k]==a[i])flag=0;
     for(k=1;flag&&k     if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
     if(!flag) /*若存在矛盾不滿足要求，需要重新設(shè)置第i個(gè)元素*/
     {
     if(a[i]==a[i-1]) /*若a[i]的值已經(jīng)經(jīng)過(guò)一圈追上a[i-1]的值*/
     {
     i--; /*退回一步，重新試探處理前一個(gè)元素*/
     if(i>1&&a[i]==NUM)
     a[i]=1; /*當(dāng)a[i]為NUM時(shí)將a[i]的值置1*/
     else if(i==1&&a[i]==NUM)
     not_finish=0; /*當(dāng)?shù)谝晃坏闹颠_(dá)到NUM時(shí)結(jié)束*/
     else a[i]++; /*將a[i]的值取下一個(gè)值*/
     }
     else if(a[i]==NUM) a[i]=1;
     else a[i]++; /*將a[i]的值取下一個(gè)值*/
     }
     else if(++i<=NUM)
     if(a[i-1]==NUM) a[i]=1; /*若前一個(gè)元素的值為NUM則a[i]=1*/
     else a[i]=a[i-1]+1; /*否則元素的值為前一個(gè)元素的下一個(gè)值*/
     }
     if(not_finish)
     {
     ++count;
     printf((count-1)%3?" [%2d]: ":" \n[%2d]: ",count);
     for(k=1;k<=NUM;k++) /*輸出結(jié)果*/
     printf(" %d",a[k]);
     if(a[NUM-1]     else a[NUM-1]=1;
     i=NUM-1; /*開(kāi)始尋找下一個(gè)足條件的解*/
     }
     }
    }