八皇后问题的解决方案是使用回溯法，即逐行放置皇后并检查列与对角线冲突，若无法继续则回退至上一行尝试其他列；通过列、主副对角线标记数组可将冲突检测优化至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种皇后排列（这还不包括非法的放置方式），回溯法通过其内在的剪枝机制，大大减少了需要探索的状态空间。它避免了大量无谓的计算，因为它在很早期就能识别出无效的布局。这让它不仅仅是一种算法，更像是一种解决这类组合问题的思维模式：遇到死路就回头，直到找到正确的方向。这种“试探-验证-回溯”的循环，对于这种一步步构建解决方案的问题来说，简直是天作之合。
实际实现中，我们如何高效地检查冲突？
在回溯法的实际编码过程中，高效地检查冲突是性能的关键。刚才提到了行、列、对角线三种冲突，行冲突通过“一行只放一个皇后”的策略自然解决。剩下的就是列和对角线。
最直观的方法是，每当我们在
(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 寻找一个解：八皇后问题通常是寻找所有可能的解。但有时，我们可能只关心是否存在一个解，或者找到第一个解即可。回溯法可以轻易地在这两种模式之间切换。
- 最小冲突问题：这不是经典的八皇后问题，而是它的一个变种。给定一个初始的皇后布局（可能存在冲突），目标是通过最少步移动来消除所有冲突。这通常会用到局部搜索算法，如爬山法或模拟退火，而不是纯粹的回溯。但即便如此，对冲突的理解（基于行、列、对角线）依然是基础。
回溯法在这些变体中，依然扮演着至关重要的角色。它提供了一个系统性的框架，用于探索具有复杂约束的解空间。无论问题如何变化，只要它能被分解成一系列决策，并且每个决策都需要满足某些条件，那么回溯法几乎总是一个值得考虑的强大工具。它教会我们的，不仅仅是如何解决一个特定的棋盘问题，更是如何有条不紊地处理复杂的组合优化与搜索问题。
