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

柿子饼同学

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, ans = 0, cnt = 1; // n个皇后, ans个解法
   
5. int xys[15] = {0}; // 它的下标是 行 , 存储的值是 列
   
6. 
   
7. bool check(int x, int y, int dep){ // 检查放的位置是否符合
   
8.     for(int i = 1; i < dep; i++){ // 同行列 , 对角线
   
9.         if(x == xys[i] || y == i || x+y == xys[i]+i || x-y == xys[i]-i) return 0;
   
10.     }
    
11.     return 1;
    
12. }
    
13. 
    
14. void print(){ // 输出
    
15.     for(int i = 1; i <= n; i++){
    
16.         cout << xys[i] << " ";
    
17.     }
    
18.     cout << endl;
    
19. }
    
20. 
    
21. void dfs(int dep){
    
22.     if(dep > n){
    
23.         if(ans <= 3) print(); // 输出前 3 组解法
    
24.         ans++; // 到头就走 , 总解法加一
    
25.         return;
    
26.     }
    
27.     else{
    
28.         for(int i = 1; i <= n; i++){
    
29.             if(check(i, dep, dep)){ // 符合条件就放
    
30.                 xys[dep] = i;
    
31.                 dfs(dep+1);
    
32.                 xys[dep] = 0; // 回溯
    
33.             }
    
34.         }
    
35.     }
    
36. }
    
37. 
    
38. int main(){
    
39.     ios::sync_with_stdio(0);
    
40. 
    
41.     cin >> n;
    
42.     dfs(1);
    
43.     cout << ans << endl;
    
44. 
    
45.     return 0;
    
46. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-6-29 15:24:23

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

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int board[14];
   
5. 
   
6. // 打印棋盘上皇后的位置
   
7. int show(int N) {
   
8.         for(int i = 1; i <= N; i++) {
   
9.                 cout << board[i] << " ";
   
10.         }
    
11.         cout << endl;
    
12.         return 0;
    
13. }
    
14. 
    
15. // 检查棋盘上的每个直线位置是否存在多个皇后
    
16. bool check(int k) {
    
17.         for (int i = 1; i < k; ++i) {
    
18.                 if ((board[i] == board[k]) or (board[i] - board[k] == k - i) or (board[i] - board[k] == i - k)) return false;
    
19.         }
    
20.         return true;
    
21. }
    
22. 
    
23. // 题解
    
24. int solution(int N) {
    
25.         int k = 1, count = 0;
    
26.         board[k] = 1; // 从 (1, 1) 开始
    
27.         while(k > 0) {
    
28.                 if(k <= N and board[k] <= N) {
    
29.                         if(not check(k)) board[k]++;
    
30.                         else {
    
31.                                 k++; // 往右移
    
32.                                 board[k] = 1; // 放置皇后
    
33.                         }
    
34.                 }
    
35.                 else {
    
36.                         if(k > N) {
    
37.                                 count++; // 计算解的总数
    
38.                                 if (count < 4) show(N); // 打印前三个解
    
39.                         }
    
40.                         k--;
    
41.                         board[k]++;
    
42.                 }
    
43.         }
    
44.         return count;
    
45. }
    
46. 
    
47. int main(void) {
    
48.         int N = 13;
    
49.         cout << solution(N);
    
50.         return 0;
    
51. }

复制代码

跳转到最佳答案楼层

桃花飞舞

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

柿子饼同学

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

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

柿子饼同学

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

傻眼貓咪

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

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int board[14];
   
5. 
   
6. // 打印棋盘上皇后的位置
   
7. int show(int N) {
   
8.         for(int i = 1; i <= N; i++) {
   
9.                 cout << board[i] << " ";
   
10.         }
    
11.         cout << endl;
    
12.         return 0;
    
13. }
    
14. 
    
15. // 检查棋盘上的每个直线位置是否存在多个皇后
    
16. bool check(int k) {
    
17.         for (int i = 1; i < k; ++i) {
    
18.                 if ((board[i] == board[k]) or (board[i] - board[k] == k - i) or (board[i] - board[k] == i - k)) return false;
    
19.         }
    
20.         return true;
    
21. }
    
22. 
    
23. // 题解
    
24. int solution(int N) {
    
25.         int k = 1, count = 0;
    
26.         board[k] = 1; // 从 (1, 1) 开始
    
27.         while(k > 0) {
    
28.                 if(k <= N and board[k] <= N) {
    
29.                         if(not check(k)) board[k]++;
    
30.                         else {
    
31.                                 k++; // 往右移
    
32.                                 board[k] = 1; // 放置皇后
    
33.                         }
    
34.                 }
    
35.                 else {
    
36.                         if(k > N) {
    
37.                                 count++; // 计算解的总数
    
38.                                 if (count < 4) show(N); // 打印前三个解
    
39.                         }
    
40.                         k--;
    
41.                         board[k]++;
    
42.                 }
    
43.         }
    
44.         return count;
    
45. }
    
46. 
    
47. int main(void) {
    
48.         int N = 13;
    
49.         cout << solution(N);
    
50.         return 0;
    
51. }

复制代码

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免杀等设定。