八皇後問題解法

八皇後問題是一個比較有意思的問題.
在一個8x8的棋盤上,如何擺放8個祺子才能使皇後無法相互攻擊.
每一行,每一列,每一條斜線都只能有一個皇後.
列出所有的擺法

有一個比較簡單的方法是
將每一個皇後編上號1,2,3,4,5,6,7,8, 然後列出這8個數的全排列,
可以得到每行,每列都只有一個後的擺法,再替除斜率等於1的輸出.
如何輸出全排列,有好幾種算法, 可以用google搜索找到答案

char  data[8]  ;
data[n]    存放第n個棋子擺放在第一排的位置 .  n< 8,  data[n] <8

檢查是否同一斜線

int king_valid(char *str)
{
        int i,j;
        int loop;
        for(i=1; i<8; i++) {
                 loop=8-i;
                 for(j=0; j<loop; j++) {
                         if (abs(str[j]-str[j+i]) == i) {
                                 return 0;
                         }
                 }
        }
        return 1;
}


當然這樣做的效率不怎麼高.

解法二:回溯法
用回溯法處理要快一點.
原理很簡單,
先放一個, 然後放第2個, 第3個,
如果找不到位置, 退回前一列,尋找下一個擺放位置.

為了解決, 擺n個皇後如何處理, 用了一個變數

[code]
  1 #include
  2 #include
  3 #include
  4
  5 void king_dump(char *str, int size)
  6 {
  7         int i;
  8
  9         for(i=0; i 10                  printf("%2d ", str[i] )  ;
 11         }
 12         printf("\n");
 13         /*
 14         char buf[20] ;
 15         buf[size] = 0;
 16
 17         for (i=0; i 18                  memset(buf,'-', size);
 19                  buf[str[i]-1] = '1';
 20                  printf("%s\n",buf);
 21         }
 22         printf("\n");
 23         */
 24
 25
 26 }
 27
 28
 29
 30 int  nking_valid(char *str, int size)
 31 {
 32          int i;
 33          int j = size -1;
 34         /*是否同一斜線,或相等
 35           前面的已經符合規則, 只需判斷最後一個
 36          */
 37
 38          char ch = str[size-1] ;
 39
 40          for(i=0;   i 41                  if (ch == str[i] || abs(ch - str[i]) == j ) {
 42                          return 0;
 43                  }
 44          }
 45          return 1;
 46 }
 47
 48
 49 int nking_next(char *data, int *cur, int max)
 50 {
 51          int i ;
 52          int len = *cur + 2 ;
 53
 54          i = data[len-1] ;
 55          i++;
 56          for (; i<= max ;   i++) {
 57                  data[len-1] =i ;
 58                  if (nking_valid(data, len ) ==1) {
 59                          (*cur)++;
 60                          return 1 ;
 61                  }
 62          }
 63
 64
 65          data[len-1] = 0 ;
 66          /* back trace*/
 67          (*cur) -- ;
 68          return 0;
 69 }
 70
 71 /*
 72    0:空
 73    num: 皇後位置
 74    nking:  回溯法
 75 */
 76
 77
 78 int nking(int nk)
 79 {
 80          char  data[30]={0} ;
 81          int pos =0;
 82          data[0] =1 ;
 83          int lim=nk -1 ;
 84
 85          if (nk>=30) {
 86                  return 0;
 87          }
 88          while (data[0] <=  nk) {
 89                  if (nking_next(data, &pos, nk) ==1) {  /* found corret pos */
 90                          if (pos == lim ) {
 91                                  king_dump(data, nk) ;
 92                                  pos --;
 93                          }
 94                          continue ;
 95                  }
 96                  /* error */
 97                  if (pos <0) {
 98                          pos = 0;
 99                          data[0] +=1 ;
100                  }
101          }
102          return 0;
103 }
104
105
106 int main(int argc, char *argv[])
107 {
108          int i = 8;
109          if (argc>1) {
110                  i =atoi(argv[1]) ;
111
112          }
113
114          nking(i);
115          exit(0);
116
117 }
118
[/code]