现在的位置: 首页 > 综合 > 正文

八皇后问题——回溯法解决

2013年04月17日 ⁄ 综合 ⁄ 共 617字 ⁄ 字号 评论关闭

在8X8个格子里,放置8个皇后。要求这8个皇后任意两个 不在同一行,不在同一列,不在对角线上。

参考代码如下:

#include<stdio.h>
#include<math.h>
int X[9]={0}; //X[0]是备用的。

int place(int k)
{
 int i;
 for(i=1;i<k;i++)
 {
  if( (X[i]==X[k]) || (abs(X[i]-X[k])==abs(i-k)) )
  {
   return 0;
  }
 }
 return 1;
}

void N8Queens(void)
{
 int k;
 k=1;
 while(k>0)
 {
  X[k]++;
  while((X[k]<=8) && (!place(k)) ) //找到k行一个有效的位置
  {
   X[k]++;
  }
  if(X[k]<=8)
  {
   if(k==8)  //说明8个皇后排好了
   {
    return;
   }
   else
   {
    k++; //准备排下一行!下一行也是需要从第一列开始。
    X[k]=0; 
   }

  }

  else  //说明当前行没有位置可以放,需要回溯到上一行!
  {
   X[k]=0; //因为要返回上一行,所以当前行已经无效了!
   k--;
  }
 }
}

int main()
{
 int i;
 N8Queens();
 for(i=1;i<=8;i++)
 {
  printf("%d\n",X[i]);
 }
 return 0;
}

 

抱歉!评论已关闭.