[C++实现]八皇后问题

这篇具有很好参考价值的文章主要介绍了[C++实现]八皇后问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题意解析

国际象棋中的皇后,可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后,使得任意两个皇后都不在同一条横线、竖线、斜线方向上?八皇后问题是一个古老的问题,于1848年由一位国际象棋棋手提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,如何求解?以高斯为代表的许多数学家先后研究过这个问题。后来,当计算机问世,通过计算机程序的运算可以轻松解出这个问题。 

二、如何解决八皇后问题?

        所谓递归回溯,本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后,摆放成功后,递归一层,再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放,则向右移动一格再次尝试,如果摆放成功,则继续递归一层,摆放第三个皇后......

  如果某一层看遍了所有格子,都无法成功摆放,则回溯到上一个皇后,让上一个皇后右移一格,再进行递归。如果八个皇后都摆放完毕且符合规则,那么就得到了其中一种正确的解法。说起来有些抽象,我们来看一看递归回溯的详细过程。

1.第一层递归,尝试在第一行摆放第一个皇后

[C++实现]八皇后问题

 2.第二层递归,尝试在第二行摆放第二个皇后(前两格被第一个皇后封锁,只能落在第三格):

[C++实现]八皇后问题

3.第三层递归,尝试在第三行摆放第三个皇后(前四格被第一第二个皇后封锁,只能落在第五格):

[C++实现]八皇后问题

4.第四层递归,尝试在第四行摆放第四个皇后(第一格被第二个皇后封锁,只能落在第二格):

[C++实现]八皇后问题

5.第五层递归,尝试在第五行摆放第五个皇后(前三格被前面的皇后封锁,只能落在第四格): 

[C++实现]八皇后问题

 6.由于所有格子都“绿了”,第六行已经没办法摆放皇后,于是进行回溯,重新摆放第五个皇后第八格

[C++实现]八皇后问题

7.第六行仍然没有办法摆放皇后,第五行也已经尝试遍了,于是回溯到第四行,重新摆放第四个皇后第七格: 

[C++实现]八皇后问题

 8.继续摆放第五个皇后,以此类推......

 三、八皇后问题的代码实现

解决八皇后问题,可以分为两个层面:

1.找出第一种正确摆放方式,也就是深度优先遍历。

2.找出全部的正确摆放方式,也就是广度优先遍历。

 我们本篇只介绍如何找出第一种正确摆放方式。具体代码如下:

//"八皇后问题回溯实现"
#include <iostream>
using namespace std;
const int ArSize = 8;//这个数等于几,就是几皇后。
int num = 0;
void solve(bool arr[ArSize][ArSize], int row);
bool check(bool arr[ArSize][ArSize], int row, int column);
void outPut(bool arr[ArSize][ArSize]);

int main()
{
    bool chessboard[ArSize][ArSize];
    // 数组初始化
    for (auto &i : chessboard)
    {
        for (auto &j : i)
        {
            j = false;
        }
    }
    solve(chessboard, 0);
    cout << "八皇后问题共有" << num << "种解!" << endl;
    system("pause");
    return 0;
}
// 回溯法
void solve(bool arr[ArSize][ArSize], int row)
{
    for (int column = 0; column < ArSize; ++column)
    {
        arr[row][column] = true;
        if (check(arr, row, column))
        {
            if (row + 1 == ArSize)
            {
                outPut(arr);
            }
            else
            {
                solve(arr, row + 1);
            }
        }
        arr[row][column] = false;
    }
}
// 判断皇后的落点是否合规
bool check(bool arr[ArSize][ArSize], int row, int column)
{
    if (row == 0)
    {
        return true;
    }
    int i, j;
    // 判断纵向是否有冲突
    for (i = 0; i < row; ++i)
    {
        if (arr[i][column])
        {
            return false;
        }
    }
    i = row - 1;
    j = column - 1;
    // 判断正斜对角线是否有冲突
    while (i >= 0 && j >= 0)
    {
        if (arr[i][j])
        {
            return false;
        }
        --i;
        --j;
    }
    i = row - 1;
    j = column + 1;
    // 判断负斜对角线是否有冲突
    while (i >= 0 && j <= ArSize - 1)
    {
        if (arr[i][j])
        {
            return false;
        }
        --i;
        ++j;
    }
    return true;
}
// 打印每种正确的解法
void outPut(bool arr[ArSize][ArSize])
{
    ++num;
    cout << "**********************" << num << "*********************" << endl;
    for (int i = 0; i < ArSize; ++i)
    {
        for (int j = 0; j < ArSize; ++j)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    cout << "*********************************************" << endl;
}

输出结果的部分截图如下:

[C++实现]八皇后问题文章来源地址https://www.toymoban.com/news/detail-464539.html

到了这里,关于[C++实现]八皇后问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 递归求解n皇后问题的解析和求解(矩阵储存版)

    1. n皇后问题问题描述 ​ n皇后问题来源于著名的十九世纪著名数学家提出的八皇后问题。问题为:在8×8的棋盘上摆放八个皇后,皇后之间不能互相攻击,既任意两个皇后不在同一行、同一列,也不再同一斜线上。n皇后则是在八皇后的基础上,将棋盘扩充为n×n,皇后的数量也

    2024年01月19日
    浏览(36)
  • Java实现八皇后问题

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出:在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 第一个皇后先

    2024年02月14日
    浏览(29)
  • [C++实现]八皇后问题

    一、题意解析 国际象棋中的皇后,可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后,使得 任意两个皇后都不在同一条横线、竖线、斜线方向上 ?八皇后问题是一个古老的问题,于1848年由一位国际象棋棋手提出:在8×8格的国际象棋上摆放八个皇后,使其不能

    2024年02月06日
    浏览(28)
  • DFS(深度优先遍历、N皇后问题、2N皇后问题)

    目录 一、回溯法与深度优先搜索(DFS) 二、DFS与二叉树的前序遍历 2.1、二叉树的前序遍历 2.2、DFS 全排列  2.3、分析 三、N皇后问题 1. 回溯法: 是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解的话(或者至少不是最后一个解),回溯法

    2024年03月21日
    浏览(54)
  • 符号三角形-计算机算法设计与分析【1600+字解析 dfs全排列 列举情况】【题意分析】【算法分析】【思路是怎么来的】【过程是什么】

    下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”,2个异号下面都是“-”。 在一般情况下,符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 题意分析 也就是 给

    2024年02月03日
    浏览(37)
  • 回溯法--n皇后问题

    回溯法有两个模板--子集树、排列树,他们有回溯法的共同特点:深度优先搜索,如果一条路走不通,再退回来(类似递归) 八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔(Max Bezzel)于1848年提出。第一个解在1850年由弗朗兹·诺克(Franz Nauck)给出。并且将其推广为更一般

    2024年02月02日
    浏览(54)
  • Python 解决八皇后问题

       八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题:这时棋

    2024年02月06日
    浏览(49)
  • 八皇后问题(回溯法)

    目录 什么是八皇后 八皇后问题怎么解决? 什么是回溯法 回溯法的模板 八皇后问题的核心代码 判断皇后位置是否可行 总体实现代码 每日一句: 种一棵树的最好时间是十年前,其次是现在。 八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的

    2023年04月09日
    浏览(40)
  • 四皇后问题(多种方法)

    问题描述 : 以4皇后为例,其他的N皇后问题以此类推。所谓4皇后问题就是求解如何在4×4的棋盘上无冲突的摆放4个皇后棋子。在国际象棋中,皇后的移动方式为横竖交叉的,因此在任意一个皇后所在位置的水平、竖直、以及45度斜线上都不能出现皇后的棋子。 回溯法 : dfs

    2024年02月04日
    浏览(24)
  • 回溯法求解八皇后问题

    问题提出 :八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850 提出在 8x8 格的国际象棋上摆放八皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志

    2023年04月08日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包