搜索八皇后问题

ゞ浴缸里的玫瑰 2021-12-15 04:57 238阅读 0赞

八皇后问题:

问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法

搜索经典题。

难的点在于想出对角线的标记。

![1369989-20190309153857861-1654794242.png][]

首先在棋盘上建立坐标（i,j）;

![1369989-20190309154052010-1449712988.png][]

可以放斜率为正(从左下到右上的直线  **/**

发现从左上到右下斜线排列的顺序，可以用 ***i + j***进行标记

0,1,2,3,4,5,6,7,8,9...12,13

![1369989-20190309154451468-840829277.png][]

那么类似的，我们可以推出 ***i - j***

7.6,5,4,3,2,1,0,-1 .. -6,-7

#include <iostream>
    using namespace std;
    
        int ans = 0;
        const int MAXN = 8;
        bool row[MAXN],x1[MAXN*2],x2[MAXN*2];
        
    bool check(int c,int i){
        //检测是否在对角线以及这行有皇后 
        return !row[i] && !x1[c+i] && !x2[c-i+MAXN];
    }
    
    void dfs(int c){
        //在c行i列放皇后 
        if(c == 8){
            ans++;
            return;
        }
        for(int i=0;i<8;++i){
            if(check(c,i)){
                row[i] = x1[c+i] = x2[c-i+MAXN] = true;
                dfs(c+1);
                row[i] = x1[c+i] = x2[c-i+MAXN] = false;
            }
        }
    }
    int main() {
        dfs(0);
        cout << ans << endl;
        return 0;    
    }

转载于:https://www.cnblogs.com/--zz/p/10501134.html

[1369989-20190309153857861-1654794242.png]: /images/20211214/141b0cbdc9c140da928bf550c1c3d090.png
[1369989-20190309154052010-1449712988.png]: /images/20211214/22d059a1d7da431d99431122cfbb85c0.png
[1369989-20190309154451468-840829277.png]: /images/20211214/a98021b4305543e59d43b88a219cf8d9.png

发表评论取消回复

表情：

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

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

相关阅读

相关搜索与回溯算法：八皇后问题

1213：八皇后问题时间限制: 1000 ms 内存限制: 65536 KB 提交数: 10320 通过数: 3609 【题目描述】在国际象棋棋...

系统管理员/ 2024年04月19日 08:42/ 0 赞/ 86 阅读

相关八皇后问题

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。试解出92种结果。 ![Cent

冷不防/ 2022年08月03日 00:49/ 0 赞/ 250 阅读

相关八皇后问题

一、问题描述 ![Center][] 在8x8的国际棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能同一行、同一列、同一斜线上。八皇后问题可以扩展为n

╰+哭是因爲堅強的太久メ/ 2022年07月14日 00:17/ 0 赞/ 216 阅读

相关八皇后问题

回溯法求解八皇后问题 n皇后问题：n皇后问题是指在一个n\n的国际象棋棋盘上放置n个皇后，使得这n个皇后两两不在同一行，同一列，同一条对角线上，求合法的方案数。如

小灰灰/ 2022年06月11日 08:49/ 0 赞/ 274 阅读

相关八皇后问题

枚举法 include<iostream> using namespace std; int a[9]; int check(int n,

蔚落/ 2022年06月06日 00:38/ 0 赞/ 228 阅读

相关八皇后问题

即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。由于皇后们是不能放在同一行的，所以我们可以去掉“行”这个因素，即我第1次考虑把皇后放在第1行的某

柔情只为你懂/ 2022年05月28日 01:47/ 0 赞/ 238 阅读

相关八皇后问题

　在国际象棋中，皇后是最强大的一枚棋子，可以吃掉与其在同一行、列和斜线的敌方棋子.八皇后问题是这样一个问题：将八个皇后摆在一张8\8的国际象棋棋盘上，使每个皇后都无法吃掉别的皇

Bertha 。/ 2022年05月18日 05:58/ 0 赞/ 226 阅读

相关八皇后问题

include <iostream> include <cmath> include <cstring> using namespace std

港控/mmm°/ 2022年01月31日 00:29/ 0 赞/ 296 阅读

相关搜索八皇后问题

八皇后问题: 问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或

ゞ浴缸里的玫瑰/ 2021年12月15日 04:57/ 0 赞/ 239 阅读

相关八皇后问题

八皇后问题，以国际象棋为背景：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任意两个皇后都不能处于

叁歲伎倆/ 2021年09月25日 15:34/ 0 赞/ 460 阅读