用回溯法求解八皇后问题

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在8×8的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题,即在n×n的棋盘上摆放n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上。例如,八皇后问题的一个解为:

                                                       

用回溯法求解八皇后问题

显然,棋盘的每一行上可以而且必须摆放一个皇后,所以,n皇后问题的可能解用一个n元向量X=(x1,x2, …,xn)表示,其中,1≤i≤n并且1≤xi≤n,即第i个皇后放在第i行第xi列上。

        由于两个皇后不能位于同一列上,所以,解向量X必须满足约束条件:

                                xi≠xj                                  (式1)

若两个皇后摆放的位置分别是(i, xi)和(j, xj),在棋盘上斜率为-1的斜线上,满足条件i-j= xi-xj,在棋盘上斜率为1的斜线上,满足条件i+j= xi+xj,综合两种情况,由于两个皇后不能位于同一斜线上,所以,解向量X必须满足约束条件:

                            |i-xi|≠|j-xj|              (式2)

 

为了简化问题,下面讨论四皇后问题。

        四皇后问题的解空间树是一个完全4叉树,树的根结点表示搜索的初始状态,从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置,从第2层结点

到第3层结点对应皇后2在棋盘中第2行的可能摆放位置,依此类推。

回溯法求解4皇后问题的搜索过程

 

用回溯法求解八皇后问题

 

下面附上八皇后问题的C代码,八皇后问题一共有92种方案

#include <stdio.h>
#include <math.h>

#define N_QUEENS 8

void Queen();
int Place(int * x, int k);

int solutions = 0; //总的解决方案数目

int main(void)
{
 Queen();
 printf("Total %d solutions\n", solutions);

return 0;
}

void Queen()
{
 int i, k;
 int x[N_QUEENS+1]; //为了表述方便,我们不使用x[0],因此数组大小多加1

k = 1;
 for (i = 1; i <= N_QUEENS; i++)//初始化
  x[i] = 0;

while (k >= 1)
 {
  x[k]++;//在下一列放置第k个皇后

while (x[k] <= N_QUEENS && !Place(x, k))
   x[k]++;//只要有冲突,就搜索下一列,试图找到第一个不冲突的


  if (x[k] > N_QUEENS)//这说明第k行所有的都冲突,重置x[k],回溯,这两行代码才是关键
  {
   x[k] = 0;      
   k--;
  }
  else if(k < N_QUEENS)//放置下一个皇后
  {
   k++;       
  }
  else // 得到一个解,输出
  {
   for (i = 1; i <= N_QUEENS; i++)
    printf("%d, ", x[i]);
   printf("\n");

solutions++;
  // return;  //如果只想得到一个解,而不是所有的解,那么需要return 语句
  }
 }

}

int Place(int * x, int k)//考察皇后k放置在x[k]列是否发生冲突,发生冲突返回0,否则返回1
{
 int i;

for (i = 1; i < k; i++)
  if (x[k] == x[i] || abs(k-i) == abs(x[k]-x[i]))
   return 0;

return 1;
}

参考 资料 :北京科技大学 罗熊 《算法设计与分析》课件 第6章 回溯法

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/abeed9fc1932b997dae7b0fb8e56b4a4.html