这是一篇关于经典算法问题的技术解析文章。本文将通过Java代码实现N皇后问题，并详细解释回溯算法的核心思想。
具体题目在力扣-52N皇后

问题定义

N皇后问题是一个经典的组合数学与回溯算法问题，要求在N×N的棋盘上放置N个皇后，使得它们互不攻击。根据国际象棋规则，皇后可以攻击同一行、同一列或同一对角线上的其他棋子，因此需要满足以下约束条件：

  • 行约束：任意两个皇后不能位于同一行
  • 列约束：任意两个皇后不能位于同一列
  • 对角线约束：任意两个皇后不能位于同一对角线（包括主对角线和副对角线）

问题形式化

给定一个整数N，求所有可能的皇后放置方案，使得：

  1. 每行恰好有一个皇后
  2. 每列恰好有一个皇后
  3. 任意两个皇后不在同一对角线上

问题特性

  • NP完全问题：随着N增大，解空间呈指数级增长，没有已知的多项式时间解法
  • 组合爆炸：当N=8时，已有92种解；N=20时解数量已超过百万
  • 对称性：棋盘具有旋转和镜像对称性，部分解可通过对称变换得到

经典案例

N值 棋盘规模 已知解数量 特殊性质
1 1×1 1 平凡解
2 2×2 0 无解
3 3×3 0 无解
4 4×4 2 最小有解
8 8×8 92 标准棋盘
20 20×20 >100万 计算挑战

应用场景

虽然看似是游戏理论问题，但N皇后问题在计算机科学中有重要价值：

  • 算法教学：回溯/剪枝的经典案例
  • 并行计算：测试分布式算法性能
  • 约束满足：验证SAT求解器效率
  • 密码学：作为NP完全问题的代表

变种问题

研究者提出了多种扩展版本：

  • 部分皇后问题：放置K<N个皇后
  • 三维皇后问题：在立方体棋盘上放置
  • 移动皇后问题：允许皇后按特定规则移动后仍满足约束
  • 加权N皇后：为不同位置赋予权重求最优解

算法选择

使用回溯算法通过递归+剪枝寻找所有合法解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class Solution {
    //n皇后问题 分析
    /*
        1.行列都只能出现一次
        2.斜方向也只能出现一次
        3.'Q' 皇后存在
     */
     List<List<String>> list =new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] arr=new char[n][n];
        for(char[] c:arr)Arrays.fill(c,'.');
        for(int i=0;i<n;i++){
            arr[0][i]='Q';
            huisu(arr,1);
            arr[0][i]='.';
        }
        return list;
    }
    //定义错误
    //传入参数 坐标 数组 
    //返回 判断可不可以放
    private boolean isFan(int x,int y,char[][] arr){
        int n=arr.length;
        //行列
        for(int i=0;i<arr.length;i++)
         if('Q'==arr[x][i]||'Q'==arr[i][y])
          return false;
        //斜方向 思考 x y 跟斜方向有什么关系
        //关系1 左上 [x-min(x,y)][y-min(x,y)] 正确
        //关系2 右上 [x-min(x,arr.length-1-y)][y+min(x,arr.length-1-y)]
        int lx=x-Math.min(x,y),ly=y-Math.min(x,y);
        while(lx<n&&ly<n){
            if(arr[lx][ly]=='Q')
            return false;
            lx++;ly++;
        }
        int rx=x-Math.min(x,n-1-y),ry=y+Math.min(x,n-1-y);
        while(rx<n&&ry>=0){
            if(arr[rx][ry]=='Q')
             return false;
            rx++;ry--;
        }
        return true;
    }
    //进行回溯 传入数组就可以了 k代表行数
    private void huisu(char[][] arr,int k){
        if(k==arr.length){
            List<String> list1=new ArrayList<>();
            for(char[] z:arr){
                String s=new String(z);
                 list1.add(s);
            }
            list.add(new ArrayList<>(list1));
            return;
        }

        for(int i=0;i<arr.length;i++){
            if(isFan(k,i,arr)){
                arr[k][i]='Q';
                huisu(arr,k+1);
                arr[k][i]='.';
            }
        }
    }
}