Code666 (代码贴、代码片段)

[C] 八皇后问题 →→→→→进入此内容的聊天室

来自 , 2020-10-24, 写在 C, 查看 129 次.
URL http://www.code666.cn/view/2a34abd6
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define N 8
  4.  
  5. /*八皇后 ： 西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上？*/
  6. /*解法 ： 关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中,不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。*/
  7.  
  8. int column[N+1];// 同栏是否有皇后，1表示有
  9. int rup[2*N+1];// 右上至左下是否有皇后
  10. int lup[2*N+1];// 左上至右下是否有皇后
  11. int queen[N+1]={0};
  12. int num;// 解答编号
  13.  
  14. void backtrack ( int );// 递回求解
  15.  
  16. int main ( void )
  17. {
  18.         int i;
  19.         num=0;
  20.  
  21.         for ( i=1; i<=N; i++ )
  22.                 column[i]=1;
  23.  
  24.         for ( i=1; i<=2*N; i++ )
  25.                 rup[i]=lup[i]=1;
  26.  
  27.         backtrack ( 1 );
  28.  
  29.         return 0;
  30. }
  31.  
  32. void showAnswer()
  33. {
  34.         int x,y;
  35.         printf ( "\n解答%d\n",++num );
  36.         for ( y=1; y<=N; y++ )
  37.         {
  38.                 for ( x=1; x<=N; x++ )
  39.                 {
  40.                         if ( queen[y]==x )
  41.                         {
  42.                                 printf ( "Q" );
  43.                         }
  44.                         else
  45.                         {
  46.                                 printf ( "." );
  47.                         }
  48.                 }
  49.                 printf ( "\n" );
  50.         }
  51. }
  52.  
  53. void backtrack ( int i )
  54. {
  55.         int j;
  56.  
  57.         if ( i>N )
  58.         {
  59.                 showAnswer();
  60.         }
  61.         else
  62.         {
  63.                 for ( j=1; j<=N; j++ )
  64.                 {
  65.                         if ( column[j]==1&&
  66.                                 rup[i+j]==1&&lup[i-j+N]==1 )
  67.                         {
  68.                                 queen[i]=j;
  69.                                 // 设定为占用
  70.                                 column[j]=rup[i+j]=lup[i-j+N]=0;
  71.                                 backtrack ( i+1 );
  72.  
  73.  
  74.                                 column[j]=rup[i+j]=lup[i-j+N]=1;
  75.                         }
  76.                 }
  77.         }
  78. }

回复 "八皇后问题"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666