N皇后递归

我不是女神ヾ 2022-06-18 08:47 242阅读 0赞 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. void NQueen( int k); 
  4. int queenPos[1000];
  5. int N; 
  6. int main()
  7. {   
  9.     cin >> N; 
  10.     NQueen(0);
  11.     return 0;   
  12. }
  13. void NQueen( int k) { //在0~k-1行皇后已经摆好的情况下,摆第K行及其后皇后的位置 
  14.     int i;
  15.     if( k == N) {   // N个皇后已经摆好 
  16.         for( i = 0; i < N; i++)
  17.                 cout << queenPos[i] + 1 << " ";
  18.         cout << endl;
  19.         return ;
  20.     } 
  21.     for( i = 0; i < N; i++) {   //逐尝试第K个皇后的位置
  22.         int j;
  23.         for( j = 0; j < k; j++) {
  24.             //和已经摆好的k个皇后的位置比较,看是否冲突
  25.             if( queenPos[j] == i || //判断同一列 
  26.                     abs(queenPos[j] - i) == abs(k-j)) { //判断斜 
  27.                         break;  //冲突,则试下一个位置 
  28.                     }
  29.         } 
  30.         if( j == k) {   //符合条件 不冲突 
  31.             queenPos[k] = i;    //将第K个皇后摆放在位置i
  32.             NQueen(k+1); 
  33.         } 
  34.     }
  35. }

发表评论

表情：
评论列表 （有 0 条评论，242人围观）

还没有评论，来说两句吧...

相关阅读

    相关 递归---n皇后问题

    题目描述： 在 n x n 的棋盘上面所有的皇后不能相互攻击，即所有的皇后 既不在同一行、不在同一列，也不在同一对角线，如下图所示（以 4 x 4 的棋盘举例）： !

    蔚落蔚落/ 0 赞/ 61 阅读

    相关 【递归入门】n皇后 问题

    题目描述 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。 如何将8个皇后放在棋盘上（有8 8个方格），使它们谁也不能被吃掉！这就

    以你之姓@以你之姓@/ 0 赞/ 70 阅读

    相关 递归--八皇后

    　　八皇后这个典的问题，是每个真正程序员必须经历过的。这也是我第二次来解决这个问题了，第一次应该是学数据结构那时候吧。这次写起来顺利多了，基本没遇到什么卡壳的地方。递归+回溯。

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 416 阅读