八皇后问题是什么？回溯法解决八皇后-js教程-PHP中文网

八皇后问题的解决方案是使用回溯法，即逐行放置皇后并检查列与对角线冲突，若无法继续则回退至上一行尝试其他列；通过列、主副对角线标记数组可将冲突检测优化至O(1)，该方法可扩展至N皇后及带障碍等变体问题。

八皇后问题是什么？回溯法解决八皇后

八皇后问题，说白了，就是在8x8的棋盘上放置八个皇后，让它们彼此之间不能互相攻击。这意味着任何两个皇后都不能在同一行、同一列或同一对角线上。而回溯法，在我看来，就是一种“试错并及时止损”的聪明策略，它能系统性地探索所有可能的解决方案，同时避免走入死胡同。

解决方案

解决八皇后问题，回溯法是经典的套路。它的核心思想是：我们一行一行地放置皇后。

想象一下，我们从棋盘的第一行开始。在当前行，我们尝试把皇后放到每一个可能的列上。每放一个皇后，我们都要检查一下：这个新放的皇后会不会和之前已经放好的皇后“打架”？如果会，那这个位置就不能放，我们得换到下一列去试。如果当前列可以放，那好，我们就把皇后放在这里，然后“递归”地进入下一行，去放置下一个皇后。

如果我们在下一行尝试放置皇后时，发现所有列都不能放（因为都会和前面的皇后冲突），那这说明我们之前在某一行做的决定是错的。这时候，回溯的精髓就来了：我们会“退回”到上一行，把那个皇后从它当前的位置上拿开，然后尝试把它放到当前行的下一个可用列上。如果当前行的所有列都试过了，还是找不到合适的位置，那就继续向上回溯，直到找到一个可以改变的决策点。

这个过程会一直持续，直到我们成功地在所有八行都放上皇后（找到一个解），或者所有可能的路径都尝试过了，证明无解（虽然八皇后问题是有解的）。

具体的冲突检查逻辑是这样的：

行冲突：我们每次只在一行放一个皇后，所以天然避免了行冲突。
列冲突：检查当前要放置的列是否已经被之前的皇后占据。
对角线冲突：这是最 tricky 的部分。一个简单的数学观察是：
- 主对角线（从左上到右下）上的所有格子，它们的
```
行坐标 - 列坐标
```
  登录后复制
  的值是常数。
- 副对角线（从右上到左下）上的所有格子，它们的
```
行坐标 + 列坐标
```
  登录后复制
  的值是常数。所以，我们只需要检查新放置的皇后，它的
```
行 - 列
```
  登录后复制
  和
```
行 + 列
```
  登录后复制
  的值是否与之前任何一个皇后的相应值相同。

function solveNQueens(row, board, N):
    if row == N:
        // 所有皇后都放好了，找到一个解
        print board
        return

    for col from 0 to N-1:
        if isValid(row, col, board, N):
            board[row] = col // 在当前行放置皇后
            solveNQueens(row + 1, board, N) // 递归到下一行
            // 回溯：如果从下一行返回，说明当前放置的皇后不行，
            // 或者已经找到了所有解，这里不需要显式“移除”，
            // 因为在下一轮循环中，board[row]会被新值覆盖
            // 但如果需要找所有解，这里需要理解为“取消当前选择”
            // (board[row] = -1) 这样的操作在实际递归中是隐式的
            // 因为当函数返回后，board[row]的值在上一层调用栈中不会被影响
            // 但如果board是全局变量，则需要显式 board[row] = -1

登录后复制

为什么回溯法是解决八皇后问题的“直觉选择”？

我觉得，回溯法之所以对八皇后问题显得如此“直觉”，很大程度上是因为问题的本质就是一种“约束满足”的搜索。我们不是要计算一个值，而是要找到一个满足特定条件的配置。

想象一下你正在玩一个复杂的拼图，你每次拿起一块，都会尝试把它放到一个可能的位置。如果发现它和周围的块不匹配，你会立刻把它拿开，换一块或者换个位置。你不会把整个拼图都拼完才发现中间有一块是错的。回溯法就是这个思路，它聪明地在每一步都检查约束，一旦发现当前路径不可能通向有效解，就立刻“剪枝”，放弃这条路，转而尝试其他可能性。

相比于暴力穷举所有

8! = 40320

登录后复制

种皇后排列（这还不包括非法的放置方式），回溯法通过其内在的剪枝机制，大大减少了需要探索的状态空间。它避免了大量无谓的计算，因为它在很早期就能识别出无效的布局。这让它不仅仅是一种算法，更像是一种解决这类组合问题的思维模式：遇到死路就回头，直到找到正确的方向。这种“试探-验证-回溯”的循环，对于这种一步步构建解决方案的问题来说，简直是天作之合。

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

查看详情

实际实现中，我们如何高效地检查冲突？

在回溯法的实际编码过程中，高效地检查冲突是性能的关键。刚才提到了行、列、对角线三种冲突，行冲突通过“一行只放一个皇后”的策略自然解决。剩下的就是列和对角线。

最直观的方法是，每当我们在

(row, col)

登录后复制

位置尝试放置一个皇后时，就遍历之前所有

(prev_row, board[prev_row])

登录后复制

位置的皇后，逐一比较

col == board[prev_row]

登录后复制

（列冲突），以及

abs(row - prev_row) == abs(col - board[prev_row])

登录后复制

（对角线冲突）。这种方法在

isValid

登录后复制

函数中会有一个

O(row)

登录后复制

的时间复杂度。

然而，我们可以做得更快。我们可以使用额外的布尔数组来记录哪些列、哪些对角线已经被占据。

列冲突：我们可以用一个布尔数组
```
bool col_occupied[N]
```
登录后复制
。当我们在
```
col
```
登录后复制
列放置皇后时，就设置
```
col_occupied[col] = true
```
登录后复制
。检查时直接看
```
col_occupied[col]
```
登录后复制
。
主对角线冲突：所有在同一主对角线上的格子
```
(r, c)
```
登录后复制
，它们的
```
r - c
```
登录后复制
值是相同的。对于一个
```
N x N
```
登录后复制
的棋盘，
```
r - c
```
登录后复制
的取值范围是
```
-(N-1)
```
登录后复制
到
```
N-1
```
登录后复制
。为了用数组索引，我们可以加上
```
N-1
```
登录后复制
，使其范围变为
```
0
```
登录后复制
到
```
2*N-2
```
登录后复制
。所以，我们可以用
```
bool diag1_occupied[2*N-1]
```
登录后复制
数组，检查
```
diag1_occupied[row - col + N - 1]
```
登录后复制
。
副对角线冲突：所有在同一副对角线上的格子
```
(r, c)
```
登录后复制
，它们的
```
r + c
```
登录后复制
值是相同的。对于一个
```
N x N
```
登录后复制
的棋盘，
```
r + c
```
登录后复制
的取值范围是
```
0
```
登录后复制
到
```
2*N-2
```
登录后复制
。我们可以用
```
bool diag2_occupied[2*N-1]
```
登录后复制
数组，检查
```
diag2_occupied[row + col]
```
登录后复制
。

这样，每次

isValid

登录后复制

检查的时间复杂度就变成了

O(1)

登录后复制

，极大地提升了效率。在递归调用进入下一层之前，我们设置这些布尔值为

true

登录后复制

；在回溯时（即从递归调用返回后），我们再把它们设回

false

登录后复制

，以便探索其他路径。这种空间换时间的做法，在处理这类约束问题时非常常见且有效。

八皇后问题有哪些变体或扩展，它们与回溯法有何关联？

八皇后问题远不止于一个经典的算法谜题，它其实是更广泛的“N皇后问题”的一个特例。N皇后问题就是将棋盘大小从8x8推广到NxN，放置N个皇后。解决N皇后问题的方法和八皇后是完全一样的，只是N的值变了而已，回溯法依然是核心。

除了N皇后，这个问题的思想还可以引申出很多有趣的变体：

放置其他棋子：比如，在一个棋盘上放置最少数量的国际象棋棋子（如车、象、马），使得它们能够攻击到棋盘上的所有格子。这类问题同样可以建模为搜索问题，回溯法（或者更广义的搜索算法）依然是重要的解决思路。
带障碍的棋盘：在棋盘上设置一些不可放置棋子的障碍物，然后尝试放置皇后。这只是在
```
isValid
```
登录后复制
函数中增加了一个额外的检查条件。
寻找所有解 vs 寻找一个解：八皇后问题通常是寻找所有可能的解。但有时，我们可能只关心是否存在一个解，或者找到第一个解即可。回溯法可以轻易地在这两种模式之间切换。
最小冲突问题：这不是经典的八皇后问题，而是它的一个变种。给定一个初始的皇后布局（可能存在冲突），目标是通过最少步移动来消除所有冲突。这通常会用到局部搜索算法，如爬山法或模拟退火，而不是纯粹的回溯。但即便如此，对冲突的理解（基于行、列、对角线）依然是基础。

回溯法在这些变体中，依然扮演着至关重要的角色。它提供了一个系统性的框架，用于探索具有复杂约束的解空间。无论问题如何变化，只要它能被分解成一系列决策，并且每个决策都需要满足某些条件，那么回溯法几乎总是一个值得考虑的强大工具。它教会我们的，不仅仅是如何解决一个特定的棋盘问题，更是如何有条不紊地处理复杂的组合优化与搜索问题。

以上就是八皇后问题是什么？回溯法解决八皇后的详细内容，更多请关注php中文网其它相关文章！