剪枝在 N 皇后上省了多少

👁️ 2 人浏览 💬 0 人评论 ❤️ 添加收藏

写两个版本跑 n = 5：剪枝版放之前就用 queen_ok 查；不剪枝版把 5 行全铺满，最后才逐对检查。输出四样：剪枝解数 / 不剪枝解数 / 剪枝结点数 / 不剪枝结点数。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 四种规模各有几个解为什么不能只存 path 的地址 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Stat {
    int c = 0;   // 找到几个解
    int v = 0;   // 走过几个结点
};

bool queen_ok(const vector<int>& col, int c) {
    int r = (int)col.size();
    for (int i = 0; i < r; i++) {
        if (col[i] == c || abs(col[i] - c) == r - i) return false;
    }
    return true;
}

void queens_dfs(int n, vector<int>& col, Stat& st) {
    st.v++;
    // TODO: 剪枝版：满 n 行就计数；否则逐列试，queen_ok 过了才放
}

Stat queens(int n) {
    Stat st;
    vector<int> col;
    queens_dfs(n, col, st);
    return st;
}

bool all_ok(const vector<int>& col) {
    for (size_t i = 0; i < col.size(); i++) {
        for (size_t j = i + 1; j < col.size(); j++) {
            if (col[i] == col[j] || abs(col[i] - col[j]) == (int)(j - i)) return false;
        }
    }
    return true;
}

void raw_dfs(int n, vector<int>& col, Stat& st) {
    st.v++;
    // TODO: 不剪枝版：满 n 行再用 all_ok 检查；否则每一列都放、递归、弹出
}

Stat queens_raw(int n) {
    Stat st;
    vector<int> col;
    raw_dfs(n, col, st);
    return st;
}

int main() {
    Stat a = queens(5), b = queens_raw(5);
    cout << a.c << "/" << b.c << "/" << a.v << "/" << b.v << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

剪枝在 N 皇后上省了多少

更多题目

全部评论