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

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

八皇后：

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <algorithm>
    #include <memory.h>
    
    int n = 8;
    int total = 0;
    int c[8];
    
    bool is_ok (int row) {
        for (int j = 0; j < row; j++) {
            if (c[row] == c[j] || row - c[row] == j - c[j] || row + c[row] == j + c[j]) {
                return false;
            }
        }
        return true;
    }
    
    void queen (int row) {
        if (row == n) {
            total++;
        }
        else {
            for (int col = 0; col < n; col++) {
                c[row] = col;
                if (is_ok(row)) {
                    queen(row+1);
                }
            }
        }
    }
    
    int main (int argc, char **argv) {
        queen(0);
        printf("%d", total);
        return 0;
    }

N皇后：

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <algorithm>
    #include <memory.h>
    
    int visit[3][50];
    int a[50];
    int sum;
    int n = 8;
    
    void dfs (int row) {
        int i;
        if (row == n+1) {
            sum++;
            return;
        }
        for (i=1; i<=n; i++) {
            if (visit[0][row-i+n] == 0 && visit[1][i] == 0 && visit[2][row+i] == 0) {
                visit[0][row-i+n] = visit[1][i] = visit[2][row+i] = 1;
                dfs(row+1);
                visit[0][row-i+n] = visit[1][i] = visit[2][row+i] = 0;
            }
        }
    }
    
    int main (int argc, char **argv) {
        sum = 0;
        memset(visit, 0, sizeof(visit));
        dfs(1);
        printf("%d", sum);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

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

相关阅读

相关数据结构实验-八皇后问题

> 八皇后问题 include<iostream> include<cstring> using namespace std; //

你的名字/ 2024年04月01日 08:28/ 0 赞/ 57 阅读

相关八皇后

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

ゝ一世哀愁。/ 2022年12月24日 12:57/ 0 赞/ 123 阅读

相关八皇后

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

左手的ㄟ右手/ 2022年10月01日 11:44/ 0 赞/ 172 阅读

相关 N 皇后！

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

快来打我*/ 2022年09月12日 07:51/ 0 赞/ 289 阅读

相关八皇后

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

r囧r小猫/ 2022年08月24日 14:25/ 0 赞/ 186 阅读

相关八皇后

编写出八皇后的算法->递归算法 include <stdio.h> int nCount=0; int noDanger(int row,int

深藏阁楼爱情的钟/ 2022年08月08日 05:15/ 0 赞/ 21 阅读

相关八皇后

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

女爷i/ 2022年07月29日 10:52/ 0 赞/ 207 阅读

相关八皇后

package 搜索; import java.io.BufferedReader; import java.io.IOException;

一时失言乱红尘/ 2022年07月12日 12:14/ 0 赞/ 194 阅读

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

八皇后： include <stdio.h> include <stdlib.h> include <math.h> include <alg

￡神魔★判官ぃ/ 2022年05月31日 14:48/ 0 赞/ 217 阅读

相关回溯法——八 / N 皇后问题

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点

ゝ一世哀愁。/ 2022年04月13日 05:39/ 0 赞/ 368 阅读