八皇后问题(回溯法&枚举法)

作者 : 卿笃军

本文讨论了八皇后问题的三种解决方案:

一、枚举法

二、回溯法(递归版)

三、回溯法(非递归版)

本来这些代码是以前编写好的,没有发表,由于最近又学习到了八皇后问题,自己整理了一下发表了出来!

首先、说明一下何为八皇后问题,我也不去谷歌了,直接简单的说明一下:

八皇后问题,就是在一个8*8的平面棋盘上,要求你摆放8个棋子,要求:这8个棋子不能有2个在同一行,也不能有2个在同一列,同时一条斜线上面也不能有2个~~~~

比如:4*4的棋盘,你可以这样摆放(4皇后问题):

《八皇后问题(回溯法&枚举法)》

以上图为参照,我们分析一下,要使棋子不冲突,那算法要如何写?<喎�”/kf/ware/vc/” target=”_blank” class=”keylink”>vcD4KPHA+ztLDx72rtv7OrMr91+m9tc6q0rvOrMr91+mjrLKi08PPwsPm1eLW1re9yr3AtLHqvMfG5dfTo7o8L3A+CjxwPsq+wP2juiBhWzFdID0gMiCjrLHtyr612jHB0LXaMtDQ09DG7NfToaM8L3A+CjxwPmFbMl0gPSA0IKOsILHtyr612jLB0LXaNNDQ09DG7NfToaM8L3A+CjxwPmFbM10gPSAxIKOsILHtyr612jPB0LXaMdDQ09DG7NfToaM8L3A+CjxwPmFbNF0gPSAzIKOsse3KvrXaNMHQtdoz0NDT0Mbs19OhozwvcD4KPHA+PGJyPgo8L3A+CjxwPrrDo6y909fFt9bO9rPlzbvL47eouMPI57rOseDQtKO6o6iz5c27y+O3qKO6vs3Kx9PDwLTF0LbPwuTG5dfTzrvWw8rHt/HT68bky/zG5dfTs+XNu6OpPC9wPgo8cD6/ycTcs/bP1rXEvLjW1rPlzbvH6b/2o7o8L3A+CjxwPjGjqbXa0rvQ0NPQwb249sbl19OjrNOmuMPKx9Xi0fmx7cq+o7phWzFdID0gMSwgYVsyXSA9IDEsse3KvrXa0rvB0LrNtdq2/sHQtcS12tK70NC2vNPQxuXX06Oo1N3H0rK7v7zCxzMsNMHQo6mhozwvcD4KPHA+MqOp1ve21L3Hz9/Jz9PQMrj2xuXX06Os06a4w8rH1eLR+bHtyr6jumFbMV0gPSAyLCBhWzJdID0gMyyx7cq+tdrSu8HQtdq2/tDQo6y12rb+wdC12sj90NDOu9bDyc/T0Mbl19OhozwvcD4KPHA+M6OptM621L3Hz9/Jz9PQMrj2xuXX06Os06a4w8rH1eLR+bHtyr6jumFbM10gPSA0LCBhWzRdID0gMyyx7cq+tdrI/cHQtdrLxNDQo6y12svEwdC12sj90NDOu9bDyc/T0Mbl19OhozwvcD4KPHA+PHN0cm9uZz7XotLio7qyu7/JxNzU2sHQyc+z9s/Ws+XNu6Os0vLOqqOsztLDx8rHsLTB0LDat8W1xKGjvLSjurXa0rvB0MnPsNq3xdK7uPajrMi7uvPU2rXatv7B0MnPsNq3xS4uLi4utdrI/cHQo6zDv8HQsNq3xdK7uPbG5dfToaM8L3N0cm9uZz48L3A+CjxwPs/Cw+ax4NC0tPrC66O6o6g8c3Ryb25nPse/tfejus/Cw+az9s/WtcSyu7ncysdpu7nKx2qx7cq+tcS2vMrHwdCjurXaacHQo6y12mrB0Dwvc3Ryb25nPqOpPC9wPgo8cD48c3Ryb25nPtDQs+XNu6O6PC9zdHJvbmc+PC9wPgo8cD7K18/Io6y87LLitdrSu9DQtcQxLTjB0KOsyse38bPlzbuho8i7uvO87LLitdq2/tDQLi4uLi4uLi4uLi61sci7xuTKtbXa0rvB0LK70OjSqrzssuKjqNLyzqqw2rfFtdrSu7j2xuXX07XEyrG68qOsxuXFzMnPu7nDu9PQxuXX06Ossru/ycTcs+XNu6OpPC9wPgo8cD48L3A+CjxwcmUgY2xhc3M9″brush:java;”>for (int i = 1; i <= 8; ++i) //检测1~8行{for (int j = 1; j <= 8; ++j) //检测1~8列{if (a[i] == a[j])return “冲突”;}}return “不冲突”;对角线冲突:

这里稍微用数学分析一下,用i,j表示当前正在检测的两列(i外层for循环,j内层for循环),那么a[i] ,a[j] 的值就分别表示当前检测列棋子摆放的位置即行(每列只有1个棋子)。

如果两个棋子对角线冲突(正反对角线冲突),则必然有:

《八皇后问题(回溯法&枚举法)》

转化为代码:

?

1 2 3 4 5 6 7 8 9 for ( int i = 1 ; i <= 8 ; ++i)  //检测1~8行 {      for ( int j = 1 ; j <= 8 ; ++j) //检测1~8列      {          if ((a[i] - a[j] == i - j)  || (a[i] - a[j] == j - i))  //对角线冲突              return "冲突" ;      } } return "不冲突" ;

优化整理后的冲突判断代码就出炉了,如下所示:

?

1 2 3 4 5 6 7 8 9 //位置冲突算法 bool Chongtu( int a[], int n) //a[]位置数组,n皇后个数 {      for ( int i = 2 ; i <= n; ++i) //i:位置          for ( int j = 1 ; j <= i- 1 ; ++j) //j:位置              if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j)) //1:在一行;2:在对角线上                  return false ;   //冲突      return true ; //不冲突 }

关于内层for循环j<=i-1,因为判断第i个棋子是否冲突(摆放是否合理),我们只需要和前面i-1列校对就ok了。这样也保证了,i>j的恒成立。所以对角线冲突了简化了一下。

好了,该说明的都说明了,现在编写第一个八皇后代码~~~~

枚举法:

思想:八重枚举,枚举出所以摆放的情况(不管合理不合理),然后到第八层for里面判断当前枚举出来的情况是否合理~~~~

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <stdio.h> #include <math.h> //位置冲突算法 bool Chongtu( int a[], int n) //a[]位置数组,n皇后个数 {      int i = 0 , j = 0 ;        for (i = 2 ; i <= n; ++i) //i:位置          for (j = 1 ; j <= i- 1 ; ++j) //j:位置              if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j)) //1:在一行;2:在对角线上                  return false ;   //冲突      return true ; //不冲突 } //八皇后:枚举算法 void Queens8() {      int a[ 9 ] = { 0 }; //用于记录皇后位置:(第0行0列我们不用)。如:a[3] = 4;表示第3列第4行位置有皇后      int i = 0 ,count = 0 //用于计数        for (a[ 1 ] = 1 ; a[ 1 ] <= 8 ; ++a[ 1 ])          for (a[ 2 ] = 1 ; a[ 2 ] <= 8 ; ++a[ 2 ])              for (a[ 3 ] = 1 ; a[ 3 ] <= 8 ; ++a[ 3 ])                  for (a[ 4 ] = 1 ; a[ 4 ] <= 8 ; ++a[ 4 ])                      for (a[ 5 ] = 1 ; a[ 5 ] <= 8 ; ++a[ 5 ])                          for (a[ 6 ] = 1 ; a[ 6 ] <= 8 ; ++a[ 6 ])                              for (a[ 7 ] = 1 ; a[ 7 ] <= 8 ; ++a[ 7 ])                                  for (a[ 8 ] = 1 ; a[ 8 ] <= 8 ; ++a[ 8 ])                                  {                                      if (!Chongtu(a, 8 )) //如果冲突,则继续枚举                                          continue ;                                      else                                      {                                          printf( "第%d情况:" ,++count);                                          for (i = 1 ; i <= 8 ; ++i)                                              printf( "%d " ,a[i]); //打印某种情况                                          printf( "\n" );                                      }                                  } } //主函数 int main() {      Queens8();        return 0 ; }</math.h></stdio.h>

回溯法(递归版):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include <stdio.h> #include <math.h>   int a[ 9 ] = { 0 }; int n = 8 , count = 0 ;   //位置冲突算法 bool Chongtu( int a[], int n) //a[]位置数组,n皇后个数 {      int i = 0 , j = 0 ;        for (i = 2 ; i <= n; ++i) //i:位置          for (j = 1 ; j <= i- 1 ; ++j) //j:位置              if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j)) //1:在一行;2:在对角线上                  return false ;   //冲突      return true ; //不冲突 }   //八皇后问题:回溯算法(递归版) void Queens8( int k) //参数k:递归摆放第k个皇后 {      int i = 0 ;        if (k > n)      //k>n:即k>8表示最后一个皇后摆放完毕      {          printf( "第%d种情况:" ,++count);          for (i = 1 ; i <= n; ++i)              printf( "%d " ,a[i]); //打印情况          printf( "\n" );      }      else   //8个皇后未全部摆放完毕             {          for (i = 1 ; i <= n; ++i) //摆放第k个皇后时(转下一行)          {       //依次从列顶端开始搜索,一直到列底端,直到找到合适位置,如果未找到,自动返回上层递归(回溯)              a[k] = i;                            if (Chongtu(a,k)) //不冲突                  Queens8(k+ 1 ); //递归摆放下一个皇后          }      }      return ; }   //主函数 int main() {      Queens8( 1 ); //参数1:表示摆放第1个皇后        return 0 ; } </math.h></stdio.h>

回溯法(非递归版):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <stdio.h> #include <math.h>   //位置冲突算法 bool Chongtu( int a[], int n) //a[]位置数组,n皇后个数 {      int i = 0 , j = 0 ;        for (i = 2 ; i <= n; ++i) //i:位置          for (j = 1 ; j <= i- 1 ; ++j) //j:位置              if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j)) //1:在一行;2:在对角线上                  return false ;   //冲突      return true ; //不冲突 }   //八皇后问题:回溯法(非递归) void Queens8() {      int n = 8 ;        //8个皇后      int count = 0 ;    //记录当前第几情况      int a[ 9 ] = { 0 };   //存放皇后位置,如:a[2] = 4;表示第2列第4行有一个皇后(a[0]不用)      int i = 0 ,k = 1 //初始化k为第一列        a[ 1 ] = 0 ;         //初始化a[1] = 0            while (k > 0 )     //k==0时:表示摆放第1个皇后就超过了列底部(即已经找完所有情况)      {          a[k] += 1 ;    //a[k]位置,摆放一个皇后          while ((a[k] <= n) && (!Chongtu(a,k))) //如果a[k](即皇后摆放位置)没有到列最底部,且摆放冲突。              a[k] += 1 ; //将皇后列下移一位          if (a[k] <= n) //皇后摆放位置没有到达列最底部          {              if (k == n) //k==n表示,8列皇后全部摆放完毕              {                  printf( "第%d种情况:" ,++count);                  for (i = 1 ; i <= n; ++i) //打印情况                      printf( "%d " ,a[i]);                  printf( "\n" );              }              else      //皇后还未摆放完毕              {                  k += 1 ;    //继续摆放下一列                  a[k] = 0 //此行初始化a[k] = 0;表示第k列,从第一行开始摆放皇后              }          }          else  //回溯:当a[k]>8进入else,表示在第k列中没有找到合适的摆放位置              k -= 1 ; //回溯到k-1步:k表示第几个皇后,a[k]表示第k个皇后摆放的位置      }      return ; }   //主函数 int main() {      Queens8();        return 0 ; }</math.h></stdio.h>
    原文作者:回溯法
    原文地址: https://blog.csdn.net/u013408431/article/details/76235831
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞