回溯法-n皇后

2024-08-30 19:36
文章标签 皇后 回溯

本文主要是介绍回溯法-n皇后，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

N皇后问题

问题定义

  • 棋盘: 一个n×n的网格。
  • 皇后: 一种特殊棋子，可以攻击同一行、同一列或两条对角线上的任何棋子。
  • 目标: 在棋盘上放置n个皇后，使得它们之间没有任何一个能够攻击到对方。

问题难点

  • 确保皇后之间不在同一行或列。
  • 避免皇后在对角线上相互攻击。

在这里插入图片描述

题目分析

问题概述

在n×n的棋盘上放置n个皇后，要求它们互不攻击。我们使用一个一维数组来存储皇后的坐标。

坐标存储

  • 使用一个长度为n的整型数组 path[] 来存储皇后的坐标。
  • 数组的下标表示行，数组的值表示列。

皇后坐标示例

  • 第0个皇后坐标：(0, path[0])
  • 第1个皇后坐标：(1, path[1])
  • …
  • 第i个皇后坐标：(i, path[i])

数组选择理由

  • 使用一维数组 path[] 可以体现深度优先搜索的思想。
  • 一维数组方便进行回溯操作。

主函数设计

编写 main 函数，输入棋盘大小 n 并初始化 path[] 数组。

int main() {int n;scanf("%d", &n);// 动态分配内存，存储皇后放置的路径int* path = (int*)malloc(sizeof(int) * n);// 注意：需要在使用完毕后释放内存printf("\n最终结果为：%d种", cout); // 此处应为算法执行后的输出结果free(path); // 释放分配的内存return 0;
}

函数规划

1. choose 函数

  • 从第0行开始，逐行选择放置新皇后的坐标。

2. judge 函数

  • 判断新皇后是否可以放置在特定坐标，确保不与已放置的皇后冲突。

3. prt 函数（可选）

  • 打印棋盘格局，传入 path[] 和 n 即可。
    上述代码中的 cout 应替换为具体的算法执行后的输出结果变量，以及 malloc 后的内存需要在使用完毕后通过 free 函数释放。

函数设计概述

为了解决n皇后问题，我们需要设计以下三个核心函数：

1. choose 函数

  • 目的: 从棋盘的第一行开始，逐行放置皇后。
  • 过程: 选择每一行中可以放置皇后的列。

2. judge 函数

  • 目的: 判断新皇后是否可以放置在当前考虑的列上。
  • 条件: 确保新皇后不会与已放置的皇后在同一行、列或对角线上。

3. prt 函数（可选）

  • 目的: 打印出所有皇后的放置位置，展示棋盘的格局。
  • 输入: 路径数组 path[] 和棋盘大小 n。

函数效果预览

完成所有函数设计后，将能够实现以下效果：
在这里插入图片描述

  • 逐行放置皇后，直到所有皇后都放置完毕或找到所有可能的解决方案。
  • 通过 judge 函数确保每次放置都符合规则。
  • 使用 prt 函数可视化解决方案，便于理解和验证。

prt 函数实现

首先，我们从最简单的打印函数 prt 开始。这个函数负责打印出棋盘上皇后的位置。

函数参数

  • int* path: 指向存储皇后列坐标的数组的指针。
  • int n: 棋盘的大小。

函数逻辑

  • 通过两个嵌套循环遍历棋盘的每一行和每一列。
  • 根据 path[i] 的值判断当前位置是否有皇后，并打印相应的字符。

代码实现

void prt(int* path, int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (path[i] == j) // 如果当前位置有皇后printf("e "); // 打印 "e"elseprintf("0 "); // 否则打印 "0"}printf("\n");}printf("\n\n");
}

choose 函数实现

接下来是 choose 函数，它负责在棋盘上逐行放置皇后。

函数逻辑

  • 从第0行开始，逐行尝试放置皇后。
  • 遇到三种情况：
    1. 当前格子符合条件，记录皇后位置，进入下一行。
    2. 当前格子不符合条件，尝试同一行的下一个格子。
    3. 如果一行内所有格子都不符合条件，回溯至上一行，尝试下一个可能的位置。

首先，在第0行choose到坐标（0，0），发现符合条件，放置。

在这里插入图片描述
放置后触发情况1，进入下一行的choose，发现坐标（1，0）不可以，因为两个皇后在一列。

在这里插入图片描述
触发情况2，我们让第一行的皇后向右移动，可还是不行。
在这里插入图片描述
再次触发情况2，再次移动，发现可以，于是触发情况1，到下一行进行choose

在这里插入图片描述
但是这时候我们发现，下一行的皇后无论放到哪一列都与旧的皇后矛盾，不是同列就是对角线
在这里插入图片描述

回溯法的应用

回溯法的精髓

在n皇后问题中，如果某一步发现当前路径已经无法继续往下走，我们就需要回溯到上一步，这是回溯法的核心思想。

剪枝定义

剪枝是一种算法优化策略，它通过去除搜索树中不必要的或无用的分支来减少搜索的时间和空间复杂度。

应用场景

在回溯算法中，剪枝是一种常用的优化手段。

剪枝操作

  • 当确定某一种情况不可能出现解时，算法会直接返回，不再继续深入搜索。

剪枝的好处

  • 当第三行已经没有合适的位置放置皇后时，继续搜索第四行的位置是没有意义的。
  • 通过回溯，计算机避免了在错误路径上浪费时间，这是一种有效的剪枝策略。

避免无效搜索

  • 计算机不会继续考虑那些看似暂时符合规则，但实际上已经不符合条件子解空间的情况。
    在这里插入图片描述

我们回溯到上一行，那么上一行便进入情况2（这个格子不符合条件），皇后向右
在这里插入图片描述
发现可行，于是进入情况1，再次进入下一行搜索，搜索到一个位置。
在这里插入图片描述
继续进入下一行，发现再次全都不行，进入情况3，开始回溯。
在这里插入图片描述
如此循环往复，直到回溯到第0行向右移动，接着搜索，直到一个正确的结果出现了。
在这里插入图片描述

choose 函数设计

choose 函数是回溯算法的核心，负责在棋盘上逐行放置皇后。

函数参数

  • int* path: 已放置皇后的列坐标数组。
  • int line: 当前正在选择的行。
  • int n: 棋盘的总行数。

函数逻辑

  1. 基本情况: 如果所有行都放置了皇后，打印棋盘格局并返回。
  2. 逐列遍历: 对当前行的每一列进行遍历，尝试放置皇后。
  3. 条件判断: 使用judge函数判断新皇后是否与旧皇后冲突。
  • 流程：
    • 遍历每一列，逐列尝试放置皇后。
    • 对于每一行，检查是否可以放置皇后：
      • 情况1：如果当前位置可行（即没有与其他皇后相互攻击），则记录皇后的位置 path[line] = column，然后递归调用 choose(path, line + 1, n) 继续放置下一行的皇后。
      • 情况2：如果当前位置不可行，皇后向右移动到下一列 column++。
      • 情况3：如果所有列都尝试完毕，无法放置皇后，则回溯到上一行 return false。

示例

  • 假设 choose(path, 1, 4) 成功放置了第一个皇后在 (1, 2) 的位置，即 path[1] = 2。
  • 然后，递归调用 choose(path, 2, 4) 继续放置第二个皇后。

代码实现

int choose(int* path, int line, int n) {// 基本情况：所有皇后都放置完毕if (line == n) {prt(path, n);return 1; // 表示找到一个解决方案}// 遍历当前行的所有列for (int column = 0; column < n; column++) {// 如果当前列可以放置皇后if (judge(path, line, column)) {path[line] = column; // 记录皇后位置choose(path, line + 1, n); // 递归调用，选择下一行}}// 如果当前行无法放置皇后，则回溯return 0; // 表示当前路径不可行
}

注意事项

  • judge 函数是判断新皇后是否与已放置的皇后冲突的关键。
  • choose 函数通过递归实现，每找到一个解决方案就打印一次棋盘格局。

判断函数 judge

judge 函数用于判断新放置的皇后是否与已放置的皇后冲突。

函数目的

  • 验证新皇后的位置 (line, column) 是否与已放置的皇后位置冲突。

参数说明

  • path[]：存储已放置皇后的坐标数组。
  • line：新皇后的行号。
  • column：新皇后的列号。

皇后坐标表示

  • 第0个皇后坐标：(0, path[0])
  • 第1个皇后坐标：(1, path[1])
  • …
  • 第i个皇后坐标：(i, path[i])

判断逻辑

  1. 遍历已放置的皇后：检查每个已放置的皇后与新皇后的位置关系。
  2. 冲突判断：
    • 同行冲突：由于新皇后是在前 line-1 行放置的，所以无需检查同行。
    • 列冲突：检查新皇后的列号 column 是否与已放置的皇后列号相同。
    • 对角线冲突：通过一种巧妙的方法判断对角线是否冲突。

函数返回

  • 如果所有已放置的皇后与新皇后均不冲突，返回 true。
  • 如果存在任何冲突，返回 false。

冲突判断方法

  • 对角线冲突：通过计算两个皇后的行和列的差值是否相等来判断对角线冲突。

示例

  • 假设 path = [0, 2, 4]，新皇后的位置为 (3, 3)。
  • 遍历 path 中的每个皇后，检查与 (3, 3) 是否冲突。
  • 如果没有冲突，judge 函数返回 true。
  • 如果存在冲突，judge 函数返回 false。

对于(x1,y1)和(x2,y2)，若\left | y1 - y2 \right | == \left | x1 - x2 \right |
，则二点处于对角线上。可以分类讨论证明。至于绝对值，利用#include<math.h>中的abs函数，abs(k) == \left | k \right |

int judge(int* path, int line, int column) {// 遍历已放置的皇后，检查是否与新皇后冲突for (int i = 0; i < line; i++) {// 如果新皇后与已放置的皇后在同一列上if (path[i] == column) {// 返回false，表示存在列冲突return false;}// 如果新皇后与已放置的皇后在同一对角线上if (abs(path[i] - column) == abs(i - line)) {// 返回false，表示存在对角线冲突return false;}// 如果当前皇后与新皇后不冲突，则继续检查下一个皇后else {continue;}}// 如果遍历完所有已放置的皇后后没有发现冲突// 则返回true，表示新皇后可以放置在指定位置return true;
}

完整代码：

#include<stdio.h> // 引入标准输入输出库
#include<math.h>  // 引入数学库，用于使用绝对值函数abs
#include<malloc.h> // 引入内存分配库，用于动态内存分配// 计数器，用来存储最终有多少种放置皇后的方案
int cout = 0;// 打印函数，用于打印棋盘上皇后的放置结果
void prt(int* path, int n) {for (int i = 0; i < n; i++) { // 遍历每一行for (int j = 0; j < n; j++) { // 遍历每一列if (path[i] == j) // 如果当前位置是皇后，则打印"e"printf("e ");else // 否则打印"0"printf("0 ");}printf("\n"); // 每行结束后换行}printf("\n\n"); // 打印完一个结果后空两行
}// 判断函数，用于判断新皇后是否与已有皇后冲突
int judge(int* path, int line, int column) {for (int i = 0; i < line; i++) { // 遍历已放置的皇后// 如果新皇后与老皇后在同一列或对角线上，则返回falseif ((path[i] == column) || ((abs(path[i] - column)) == (abs(i - line))))return false;}// 如果遍历完所有已放置的皇后都没有冲突，则返回truereturn true;
}// 选择函数，用于递归选择皇后的位置
int choose(int* path, int line, int n) {if (line == n) { // 如果已经放置完所有皇后，则打印结果并计数prt(path, n);cout++;return 0;}for (int column = 0; column < n; column++) { // 尝试在当前行的每一列放置皇后if (judge(path, line, column)) { // 如果当前位置不冲突path[line] = column; // 记录皇后的位置choose(path, line + 1, n); // 递归放置下一行的皇后}}return 0;
}// 主函数，程序的入口点
int main() {int n; // 棋盘大小scanf("%d", &n); // 从标准输入读取棋盘大小// 动态分配内存，大小为n个整数，用来存储皇后的放置路径int* path = (int*)malloc(sizeof(int) * n);// 从第0行开始选择皇后的位置，棋盘大小为nchoose(path, 0, n);// 打印最终的皇后放置方案数量printf("\n最终结果为：%d种", cout);return 0; // 程序结束
}

总结

题目思路总结

  • 起始点: 从棋盘的第一行开始放置皇后。
  • 逐行放置: 按顺序逐行放置皇后，并进行冲突检查。
  • 冲突与回溯: 如果当前行无法放置皇后，回溯至上一行重新尝试。
  • 合法解的发现: 当所有行都成功放置了皇后，即找到了一个合法解。
  • 记录方式: 使用数组记录每行皇后的列位置。

具体实现策略

  • 从第一行开始，逐行尝试放置皇后。
  • 在放置每个皇后时，检查与已放置皇后的冲突情况。
  • 若发生冲突，回溯至上一行重新放置。
  • 所有行放置完毕，记录一个解决方案。

回溯法与剪枝总结

  • 回溯法: 一种通过试错枚举所有可能解的算法。
  • 剪枝: 在回溯过程中，通过特定条件避免无效搜索，优化搜索树。
  • 优化目的: 减少搜索的时间和空间消耗，提升算法效率。
  • 剪枝重要性: 作为回溯法中的重要优化手段，显著提高算法性能。

这篇关于回溯法-n皇后的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1121744。

相关文章

题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...
回溯——9.全排列

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模：题目要求给出一个数组的所有排列组合，属于典型的全排列问题，这可以用回溯法来解决。回溯法通过递归的方式，依次将数组中的每个元素放入排列中，直到生成
阅读更多...
代码训练营 Day26 | 47.排序II | 51. N-皇后 |

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(
阅读更多...
风控系统之指标回溯，历史数据重跑

风控系统之指标回溯，历史数据重跑

个人博客：无奈何杨（wnhyang） 个人语雀：wnhyang 共享语雀：在线知识共享 Github：wnhyang - Overview 回顾 默认你已经看过之前那篇风控系统指标计算/特征提取分析与实现01，Redis、Zset、模版方法。 其中已经介绍了如何利用redis的zset结构完成指标计算，为了方便这篇文章的介绍，还是在正式开始本篇之前回顾一下。 时间窗口 zset
阅读更多...
165-Stamps【回溯】

165-Stamps【回溯】

回溯 给h和k的意思是在k种邮票中选h个邮票 基本的连续邮资问题 15226160 165 Stamps Accepted C++ 0.062 2015-03-27 07:21:37 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2
阅读更多...
JAVA学习-练习试用Java实现“N皇后 II”

JAVA学习-练习试用Java实现“N皇后 II”

问题： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n ，返回 n 皇后问题不同的解决方案的数量。 示例 1： 输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。 示例 2： 输入：n = 1 输出：1 提示： 1 <= n <= 9 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同
阅读更多...
回溯——8.递增子序列

回溯——8.递增子序列

力扣题目链接 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。 示例: 输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中
阅读更多...
【代码随想录|回溯part04】

【代码随想录|回溯part04】

代码随想录|回溯part04 1、46.全排列2、47.全排列 II3.问题 总结 python 1、46.全排列 46.全排列 class Solution:def permute(self, nums):result = []self.backtracking
阅读更多...
代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合

代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合

今日内容 回溯的理论基础leetcode. 77 组合leetcode. 216 组合总和Ⅲleetcode. 17 电话号码的字母组合 回溯理论基础 回溯法也叫回溯搜索法，它是一种搜索的方式，而且只要有递归就会有回溯，回溯就是递归的副产品。 回溯说到底并不是什么非常高深的搜索方式，本质上仍然是穷举，穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点，但改变不了回溯本质就是穷举
阅读更多...
笔试，牛客.kotori和n皇后​，牛客.AOE还是单体

笔试，牛客.kotori和n皇后​，牛客.AOE还是单体

目录 牛客.kotori和n皇后​编辑 牛客.AOE还是单体 牛客.kotori和n皇后  想起来，我之前还写过n皇后的题，但是这个我开始只能想到暴力解法 判断是不是斜对角线，联想y=x+b和y=-x+b,假如在一条线上，那么他们的x和y会对应成比例，这个扫描+判断是一个O(n^2)的操作。 import java.util.*; import java.io.*;//
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2