bahuanghou--huishuo.c

八皇后经典算法 包括回溯和枚举两种方法 八皇后经典算法 包括回溯和枚举两种方法

#include "stdio.h"
 #include "conio.h"
 main()
 {
   int m[9]={0,0,0,0,0,0,0,0,0};               /* 存放棋子，及其位置 */
   int i=1,sum=0,j,k;           /* 从第一行的皇后开始处理起 */
   m[1]=1;                 /* 第一行皇后从第一列开始放起 */
   i++;              /* 处理第二行皇后 */
   while(i>0)           /* i小于零时说明已经找到所有结果，结束循环*/
   { m[i]++;
     if(m[i]>8)       /* 次行所有列都不行，回溯到上一行*/
       i=i-1;
     else
      { for(j=1,k=1;j<i;j++)         /* 判断从第一行皇后到第i行皇后位置是否合法 */
          k=k&&(m[i]!=m[j])&&(abs(i-j)!=abs(m[i]-m[j]));      /* 只要有一个不合法，k变为零*/
           if(k==1)              /* 合法 */
            { if(i==8)               /* 处理到最后一行，完成一种摆放的寻找，准备输出这种结果*/
               { sum++;
                 printf("The %dth way: ",sum);
                 for(j=1;j<=i;j++)
                  printf("%d ",m[j]);
                  printf("\n");
                  i=i-1;        /* 回溯到上一行，寻找另一种摆放方式*/
                 }
              else
               { i++;         /* 准备处理下一行*/
                 m[i]=0;      /* 下一行从第一列开始检验 */
                }
              }
        }
     }
   getch();
  }