递归算法高效检测棋盘上皇后对角线冲突

对角线冲突检测，是N皇后问题中一个无法回避的关键环节。不少初学者在此处反复碰壁——要么逻辑判断出现偏差，要么递归陷入死循环。本文将带你深入剖析一个常见误区，并给出一个清晰、可复用的递归解决方案。

在N皇后问题中，判断新放置的皇后是否与已有皇后位于同一条对角线上——看似简单，但实现代码中往往暗藏陷阱。许多初级实现倾向于将所有对角线检查逻辑集中在一个递归函数中，结果呢？要么始终返回false，要么将本无关联的皇后也误判为冲突。

举例来说，原始代码中若写成 diaCheck(r, c) 且第一步就检查 (r, c) 自身——恰好，这个位置刚刚放置了一个新皇后（值为1），那么函数自然立即返回false，无论怎么调试都无法通过。更严重的是，它还会沿着四个方向递归扩散，将整个棋盘扫描一遍，甚至不放过已访问过的空格，最终导致误报冲突或严重拖累执行效率。

问题根源在哪里？——思路不清晰。正确的做法其实相当直接：单向、线性、非回溯。从当前皇后出发，沿着每条对角线逐格推进，直至触及边界或遇到另一个皇后为止。整个过程无需回溯，也无需回头检查。

为此，推荐采用双层递归结构：

• 入口方法 diaCheck(int r, int c)：不检查 (r, c) 自身，仅负责启动四个独立的扫描方向；
• 核心递归方法 diaCheck(int r, int c, int dr, int dc)：按照固定方向 (dr, dc) 逐步推进，例如 (-1, -1) 表示向左上角移动。

下面是一个完整、健壮的实现代码，可直接应用于实际项目：

// 入口方法：启动四条对角线独立检查（跳过当前位置）
public boolean diaCheck(int r, int c) {
    return diaCheck(r - 1, c - 1, -1, -1) && // 左上
           diaCheck(r - 1, c + 1, -1, +1) && // 右上
           diaCheck(r + 1, c - 1, +1, -1) && // 左下
           diaCheck(r + 1, c + 1, +1, +1);   // 右下
}

// 核心递归方法：沿指定方向 (dr, dc) 线性检查
private boolean diaCheck(int r, int c, int dr, int dc) {
    // 边界检查：越界即安全，返回 true
    if (r < 0 || r >= board.length || c < 0 || c >= board.length) {
        return true;
    }
    // 冲突检查：若该位置已有皇后，立即返回 false
    if (board[r][c] == 1) {
        return false;
    }
    // 递归推进：沿同一方向检查下一格
    return diaCheck(r + dr, c + dc, dr, dc);
}

这里有几个关键要点需要留意：

✅ 入口不查自身：从 (r-1,c-1) 等相邻格子开始，彻底避免误判当前皇后；
✅ 方向参数化：利用 dr 和 dc 明确控制移动轨迹，每条对角线只朝单一方向延伸，不产生混乱；
✅ 短路逻辑合理：四个方向通过 && 串联，一旦任一方向发现冲突，整体立即返回false，效率显著提升；
✅ 终止条件清晰：越界表明无皇后，返回true；遇到皇后直接返回false。逻辑明确，无歧义，也不会陷入死循环。

最后说一下性能：单方向最多检查n格，时间复杂度为O(n)，递归深度同样为O(n)，空间开销完全可控。无论是代码的正确性、可读性还是运行效率，这套方案均可视为N皇后对角线校验的“标准解法”。