当前位置：首页 > news >正文

回溯法求解N皇后问题

news 来源：原创 2025/7/1 20:19:07

目录

前言

一、回溯法是什么？

二、N皇后问题描述

分析解题思路

三、算法设计

1、递归法

2、非递归法

总结

前言

本文将从递归形式和非递归形式两种方法来介绍求解N皇后问题的回溯法，后续也会更新更多有关算法分析这方面的问题欢迎大家关注~🤩

一、回溯法是什么？

定义：回溯法（Backtracking）是一种通过试探性搜索来解决问题的算法思想，主要用于解决组合问题、决策问题和枚举问题。
核心思想：“尝试-回退”——通过逐步构建可能的解，并在发现当前路径无法得到有效解时回退（回溯），尝试其他路径。

通俗的来讲其实回溯法就是一种更高效的穷举方法，而高效就体现在下面三种核心特点中：

系统性搜索：按特定顺序（如深度优先）枚举所有可能的解。
剪枝优化：在搜索过程中提前终止无效分支（如不满足约束条件时）。
递归实现：通常用递归实现试探和回退步骤。

二、N皇后问题描述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后
要求：任何两个皇后不同行，不同列也不在同一条斜线上，求给一个整数 n ，返回 n 皇后的摆法数。

例如当输入4时，对应的返回值为2，对应的两种四皇后摆位如下图所示：

分析解题思路

我们可以先固定放入一个皇后，然后再根据条件放入另一个皇后，如果我们发现放到后面已经没有位置满足放皇后的条件了就说明我们前面的摆放肯定是有误，因此我们就要返回错误的一步重新摆放皇后，也就是回溯法的基本思想。

这里要求不同行，不同列也不在同一条斜线上，那我们就可以固定每个皇后的行分别为1~n，然后我们再挑选不同的列放入皇后并且同时满足不在同一条斜线上

那其实这里提到的不同列不同斜线就是我们的剪枝条件，我们在搜索的过程中将不满足条件的枝条减去，大大提升了搜索效率；下面是剪枝条件函数的定义：

在使用回溯法的时候，我们通常要定义全局变量，这样方便我们使用递归调用，不需要频繁的传参，这里我们使用x[ i ](i=1、2、3····n)来表示第i行的皇后放在第x[ i ]列，也就是用下标表示行号，值表示列号
bool Place(int t) {for (int i = 1; i < t; i++) {if ((abs(x[t] - x[i]) == abs(t - i)) || (x[t] == x[i]) )return false;}return true;
}
如图所示，如果两个皇后在同一条直线上，则她们的横纵坐标之差的绝对值应该相同。如果两个条件有一个不满足我们就返回false，说明不需要再向下查找了，需要修改当前皇后的位置。

三、算法设计

上面我们了解了怎么剪掉不满足条件的分支，那么我们怎么判断我们找到了一个可行解呢？

还是以四个皇后为例：

如图所示，我们易知假如把1皇后放在第一列，则2皇后不能放在1、2列，可以放在第三列，但此时再往后放3皇后的时候我们发现不管放在哪里都是错误的，则此时我们应该回到2皇后处，再放到第四列尝试，后面的以此类推（大家可以自己在纸上画一画）；那么最后我们能够找到一个可行解就是找到了最后的叶节点，此时每个皇后都有位置

1、递归法

void Backtrack(int t) {if (t > n) {sum++;//说明此时已经找到一个可行解} else {for (int i = 1; i <= n; i++) {x[t] = i;if (Place(t))Backtrack(t + 1);//如果满足条件就继续往下搜索//假如不满足条件了，则返回，从这里开始进入循环，判断下一列是否满足条件}}}

2、非递归法

传递的参数可以根据题目灵活调整，这里用k表示第k行

void Backtrack(int n) {x[1] = 0;k = 1;while (k > 0) {x[k] += 1;while (x[k] <= n && !Place(k))x[k]++;//一直往后加直到找到能够放置的位置if (x[k] <= n) {//没有超出可排的范围if (k == n) //找到了一个解sum++;else {k++;x[k] = 0;//每次都从第一列开始查找}} elsek--;//如果都排到外面去了说明该行没有可防止的位置，回溯}
}

总结

回溯法是一种通过系统性试探和剪枝优化来高效穷举所有可能解的算法，其核心思想是“尝试-回退”，在解决组合问题时能显著减少无效搜索。以N皇后问题为例，算法通过递归或迭代逐行放置皇后，并利用约束条件（列、斜线冲突）剪枝，避免不必要的路径探索，从而在O(n!)的理论复杂度下实现实际高效求解。回溯法不仅适用于N皇后这类经典问题，还可推广至数独、图着色等场景，体现了“智能穷举”的算法设计思想，其平衡了代码简洁性（递归）与执行效率（迭代），是解决NP难问题的重要工具。

前言