[已解决]N皇后问题优化

柿子饼同学

我的代码贴上, 主要 n = 13 的时候超时了 , 也不是很理解题解中的二进制优化 . 可以详细解释下嘛 , 谢谢
题目::https://www.luogu.com.cn/problem/P1219
题解::https://www.luogu.com.cn/problem/solution/P1219

#include <bits/stdc++.h>
using namespace std;

int n, ans = 0, cnt = 1; // n个皇后, ans个解法
int xys[15] = {0}; // 它的下标是 行 , 存储的值是 列 

bool check(int x, int y, int dep){ // 检查放的位置是否符合
    for(int i = 1; i < dep; i++){ // 同行列 , 对角线
        if(x == xys[i] || y == i || x+y == xys[i]+i || x-y == xys[i]-i) return 0;
    }
    return 1;
}

void print(){ // 输出
    for(int i = 1; i <= n; i++){
        cout << xys[i] << " ";
    }
    cout << endl;
}

void dfs(int dep){
    if(dep > n){
        if(ans <= 3) print(); // 输出前 3 组解法
        ans++; // 到头就走 , 总解法加一
        return;
    }
    else{
        for(int i = 1; i <= n; i++){
            if(check(i, dep, dep)){ // 符合条件就放
                xys[dep] = i;
                dfs(dep+1);
                xys[dep] = 0; // 回溯
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);

    cin >> n;
    dfs(1);
    cout << ans << endl;

    return 0;
}

(话说 N 皇后只能用暴力算法嘛)

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-6-29 15:24:23

是这样吗？我也不知道对不对：

#include <iostream>
using namespace std;
 
int board[14];

// 打印棋盘上皇后的位置
int show(int N) {
        for(int i = 1; i <= N; i++) {
                cout << board[i] << " ";
        }
        cout << endl;
        return 0;
}

// 检查棋盘上的每个直线位置是否存在多个皇后
bool check(int k) {
        for (int i = 1; i < k; ++i) {
                if ((board[i] == board[k]) or (board[i] - board[k] == k - i) or (board[i] - board[k] == i - k)) return false;
        }
        return true;
}

// 题解
int solution(int N) {
        int k = 1, count = 0;
        board[k] = 1; // 从 (1, 1) 开始
        while(k > 0) {
                if(k <= N and board[k] <= N) {
                        if(not check(k)) board[k]++;
                        else {
                                k++; // 往右移
                                board[k] = 1; // 放置皇后
                        }
                }
                else {
                        if(k > N) {
                                count++; // 计算解的总数
                                if (count < 4) show(N); // 打印前三个解
                        }
                        k--;
                        board[k]++;
                }
        }
        return count;
}
 
int main(void) {
        int N = 13;
        cout << solution(N);
        return 0;
}

跳转到最佳答案楼层

桃花飞舞

就是用这种递归的方法解的，换别的方法我就不会了，我没发现二进制优化部分。如果实在不懂可以画张图。

柿子饼同学

桃花飞舞 发表于 2022-6-28 19:45
就是用这种递归的方法解的，换别的方法我就不会了，我没发现二进制优化部分。如果实在不懂可以画张图。

哦哦哦 , 普通做法我懂 , 谢谢
主要想学习下优化

柿子饼同学

用 4 个数组过了 , 但是二进制依然不会

傻眼貓咪

是这样吗？我也不知道对不对：

#include <iostream>
using namespace std;
 
int board[14];

// 打印棋盘上皇后的位置
int show(int N) {
        for(int i = 1; i <= N; i++) {
                cout << board[i] << " ";
        }
        cout << endl;
        return 0;
}

// 检查棋盘上的每个直线位置是否存在多个皇后
bool check(int k) {
        for (int i = 1; i < k; ++i) {
                if ((board[i] == board[k]) or (board[i] - board[k] == k - i) or (board[i] - board[k] == i - k)) return false;
        }
        return true;
}

// 题解
int solution(int N) {
        int k = 1, count = 0;
        board[k] = 1; // 从 (1, 1) 开始
        while(k > 0) {
                if(k <= N and board[k] <= N) {
                        if(not check(k)) board[k]++;
                        else {
                                k++; // 往右移
                                board[k] = 1; // 放置皇后
                        }
                }
                else {
                        if(k > N) {
                                count++; // 计算解的总数
                                if (count < 4) show(N); // 打印前三个解
                        }
                        k--;
                        board[k]++;
                }
        }
        return count;
}
 
int main(void) {
        int N = 13;
        cout << solution(N);
        return 0;
}

ExiaGN001

二进制优化主要是优化o(1)的指令周期数，对算法整体复杂度不构成影响（但是会更快）
建议把所有cin/cout换成scanf/pirntf会更快
在开头只引用iostream和cstdio也可增快速度
另：n皇后目前只能递归做

傻眼貓咪

ExiaGN001 发表于 2022-6-29 22:18
二进制优化主要是优化o(1)的指令周期数，对算法整体复杂度不构成影响（但是会更快）
建议把所有cin/cout换 ...

楼主已经加了 ios::sync_with_stdio(0);

柿子饼同学

ExiaGN001 发表于 2022-6-29 22:18
二进制优化主要是优化o(1)的指令周期数，对算法整体复杂度不构成影响（但是会更快）
建议把所有cin/cout换 ...

好的 , 谢谢回答

ExiaGN001

傻眼貓咪 发表于 2022-6-30 09:47
楼主已经加了 ios::sync_with_stdio(0);

C格式输入输出已经成习惯了
所以我一直都不常用cin/cout

傻眼貓咪

ExiaGN001 发表于 2022-6-30 19:44
C格式输入输出已经成习惯了
所以我一直都不常用cin/cout

ExiaGN001

傻眼貓咪 发表于 2022-6-30 20:28

主要是我电脑上一用cin/cout就会触发Windows Defender报毒
所以只能用printf,scanf,putchar,puts,getchar,gets,fprintf,fscanf这些函数

傻眼貓咪

ExiaGN001 发表于 2022-7-1 06:45
主要是我电脑上一用cin/cout就会触发Windows Defender报毒
所以只能用printf,scanf,putchar,puts,getcha ...

我不知道你的问题是不是和以下有关？希望对你有帮助。
现在的防毒软件可说是越来越敏感了，基本上只要运行代码就会触发防毒软件的，防毒软件会误以为是病毒入侵，因此杀项目。网络上很多方法，比如：Shellcode免杀等设定。