数据结构：八皇后、N皇后

￡神魔★判官ぃ 2022-05-31 14:48 275阅读 0赞

八皇后：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <memory.h>
  7. int n = 8;
  8. int total = 0;
  9. int c[8];
  11. bool is_ok (int row) {
  12.     for (int j = 0; j < row; j++) {
  13.         if (c[row] == c[j] || row - c[row] == j - c[j] || row + c[row] == j + c[j]) {
  14.             return false;
  15.         }
  16.     }
  17.     return true;
  18. }
  20. void queen (int row) {
  21.     if (row == n) {
  22.         total++;
  23.     }
  24.     else {
  25.         for (int col = 0; col < n; col++) {
  26.             c[row] = col;
  27.             if (is_ok(row)) {
  28.                 queen(row+1);
  29.             }
  30.         }
  31.     }
  32. }
  34. int main (int argc, char **argv) {
  35.     queen(0);
  36.     printf("%d", total);
  37.     return 0;
  38. }

N皇后：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <memory.h>
  7. int visit[3][50];
  8. int a[50];
  9. int sum;
  10. int n = 8;
  12. void dfs (int row) {
  13.     int i;
  14.     if (row == n+1) {
  15.         sum++;
  16.         return;
  17.     }
  18.     for (i=1; i<=n; i++) {
  19.         if (visit[0][row-i+n] == 0 && visit[1][i] == 0 && visit[2][row+i] == 0) {
  20.             visit[0][row-i+n] = visit[1][i] = visit[2][row+i] = 1;
  21.             dfs(row+1);
  22.             visit[0][row-i+n] = visit[1][i] = visit[2][row+i] = 0;
  23.         }
  24.     }
  25. }
  27. int main (int argc, char **argv) {
  28.     sum = 0;
  29.     memset(visit, 0, sizeof(visit));
  30.     dfs(1);
  31.     printf("%d", sum);
  32.     return 0;
  33. }

发表评论

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

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

相关阅读

    相关 八皇后

    八皇后问题介绍 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 172 阅读

    相关 八皇后

    八皇后 求解思路 可以将八皇后看成全排列问题，因为每次都是在某一行选择某个位置，所以不需要考虑行的问题。每次只需要求出当前行的棋子所在列。所以可以化为全排列问

    左手的ㄟ右手左手的ㄟ右手/ 0 赞/ 214 阅读

    相关 N 皇后！

    提到回溯算法那肯定离不开 n 皇后这道算法题，它实在是太经典了。 所谓 n 皇后问题 ，指的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻

    快来打我*快来打我*/ 0 赞/ 350 阅读

    相关 八皇后

    / Queen 八皇后问题 ：递归实现 1. 从第一行开始递归 2. 然后枚举当前行中的每一列， 3. 如果可以

    r囧r小猫r囧r小猫/ 0 赞/ 249 阅读

    相关 八皇后

    八皇后问题是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇

    女爷i女爷i/ 0 赞/ 263 阅读