N皇后问题：任意皇后不共行，不共列，不共斜线，请问皇后有多少种摆法_不使用函数的n皇后问题

N皇后问题：任意皇后不共行，不共列，不共斜线，请问皇后有多少种摆法？

提示：DP3：样本位置对应模型
这个题，字节跳动改编了一下，然后放到校园招聘的笔试题中考过，我见过，当时没做出来，看来N皇后问题还是没有理解透彻，今天我就来透彻搞清楚N皇后问题！！！！

---

文章目录

• N皇后问题：任意皇后不共行，不共列，不共斜线，请问皇后有多少种摆法？
• • @[TOC](文章目录)
• 题目
• 一、审题
• N皇后问题的摆法，宏观调度
• 即将往i行j列放皇后，它与0--i-1行冲突吗，实现isOK(pos, i, j)函数
• 手撕N皇后问题暴力递归代码，i行都摆不了，就需要i-1行调整去j+1列
• 咱们来试试暴力递归改写动态规划的代码
• 总结

题目

N皇后问题，N*N的棋盘上摆N个皇后，但是要求：
任意皇后不共行，不共列，不共斜线，请问皇后有多少种摆法？

---

一、审题

示例：
比如：
（1）N=1
棋盘11格子，放1个皇后，自然摆法就是1种

（2）N=2
棋盘22格子，放2个皇后，
第一个摆在0 0 位置，第二个怎么摆，都不行，都得违规，所以摆法为0种。

（2）N=3
棋盘3*3格子，放3个皇后，
第一个：摆在0 0 位置
第二个：摆在1 2位置才行，否则要么共列，要么共斜线，都不合格
第三个：没地方放了，放在第三行哪都得违规，所以摆法为0

……

---

N皇后问题的摆法，宏观调度

接着案例试
（4）M=4
棋盘4*4格子，放4个皇后，
第一个：摆在0 0 位置
第二个：摆在1 2位置才行，否则要么共列，要么共斜线，都不合格
第三个：在上一行那么决定的情况下，我这行没地方放了，放在第三行哪都得违规，所以需要上一行做出改变，去1 3位置
，我第三个皇后勉强才能在2 1位置放下，合格
第4个，又没地方放了，尴尬，由于第三个皇后没法调，所以宣告摆法为0

咱不妨设N=9呢？
我们来寻找这个题，该如何宏观调度？

为了避免行冲突，咱们每一次只在i行填写，下一次直接去i+1行填写,
我们填写在哪一列j呢？？这样，我们每次不是要填在i行j列吗？用一个一维数组pos[i]存一下j可以吧
比如你填写第一个皇后，是0行0列，那pos[0]=0
比如你填写第二个皇后，是1行3列，那pos[1]=3
即你皇后放在i行的j列，就用pos[i]=j表示

填写棋盘的函数定义为：f（n,i,pos）：填写n皇后棋盘，0–i-1行都放好了，合格的，请你在第i行放皇后，让放的i行j列不跟0–i-1行所有皇后的位置冲突，得到的合法的摆法是多少？同时，把i行的j列放入pos记录好。

来看9宫格，咱们每次只填1行，从0行开始填
（1）每一行中，j从0–N-1都看一遍，看看能否放下？合格不合格，咱们把pos和i行j列放入isOk函数判断
【isOK(pos,i,j)，pos放着前0–i-1行的所有列，这样就能判断当前新来的一行，一列合法吗？】

咱们pos当放到i=7行时，发现所有位置都不行，那就需要第i-1行，即第6行放的j加1，去j+1位置才行
其实这就是N皇后唯一的条件转移的地方，也就是i行放不了，那就需要i-1行去j+1列试试。

（2）如果能顺利填下去，知道i=N=9了，那刚刚这一路摆法就是合格的一条路径，返回1种合法的方法
（3）然后再尝试i-1行，去j+1列试试，有没有新的可能呢？有就把方法数累加到ans结果上，最后返回。

发现了没？对每一个行i开始，其实剩下的格子，都是一个规模更小的N皇后问题，递归的思路一模一样，只不过规模更小了。
这就是暴力递归的本质，规模不同的相同问题。

上面这个宏观的调度是不是很清楚了
对于f(n,pos,i)，来到n皇后棋盘i行，合法的摆法有多少？摆在哪个位置j，记录在pos中。

if (i == n) return 1;//n行都放慢了，很OK，算一种方法
int res = 0;//每次进来都清零，就不需要恢复现场了

  //否则挨个看0--j列，哪个行
  for(int j = 0; j < n; j++){
      if (isOK(pos, i, j)){
          //如果放在ij处合理，不共列和不共斜线，则记录可以放
          pos[i] = j;
          res += f(n ,pos, i + 1);//直接去i+1行摆
      }
  }
  return res;
1
2
3
4
5
6
7
8
9
10
11
12

下面咱们看看，即将往i行j列放皇后，它与0–i-1行冲突吗？
isOK(pos, i, j)函数怎么实现，这才是N皇后问题中很重要的知识点！！！

即将往i行j列放皇后，它与0–i-1行冲突吗，实现isOK(pos, i, j)函数

不妨设k取0–i-1所有的行
之前的皇后们放在哪些位置了？k行，pos[k]列
此时你想放在i行，j列，想要合法？
（1）不共行，当初我们宏观调度摆皇后的时候，决定了i行的位置，直接去i+1行摆，所以行不用检查了，每行只会有一个皇后的。
（2）不共列，这就需要咱们核查了？那就必须满足，现在的j，不会等于任何一个pos[k]（就是之前往后们所在的列pos[k]，不能等于现在的列j，否则就冲突了）
（3）不公斜线，也就是现在的皇后，不能与之前的皇后们处于同一个斜线上，这怎么表示呢？
看下面图，橘色那个三角形，图中a行b列那个位置，现在恰好就是与i行j列是共斜线的，他们之前的关系咋表示呢？
很简单：就是直角边相等的关系，必然就是处于共斜线的，也就是|i-a|=|j-b|，
这是不合法的，如果我们要合法，不共斜线，那必然要求|i-a|！=|j-b|
这里，a就是k行中的任意一个k，b是pos[k]，这个容易理解吧

其实本题的关键就在不共斜线的条件表达式！不共斜线，那必然要求|i-a|！=|j-b|，即|i-k|！=|j-pos[k]| k取所有0–i-1行，就是前面放好的皇后们，不能与现在即将要放在i j处的皇后有冲突！

好了，咱们手撕这个判断条件得代码：

//复习：
    //即将往i行j列放皇后，它与0--i-1行冲突吗，实现isOK(pos, i, j)函数
    //不妨设k取0--i-1所有的行
    //之前的皇后们放在哪些位置了？k行，pos[k]列
    //此时你想放在i行，j列，想要合法？
    public static boolean isOK(int[] pos, int i, int j){
        //检查所有的行
        for (int k = 0; k < i; k++) {
            if (j == pos[k]) return false;//共列的话，不合法
            //画图看看不共斜线，那必然要求|i-a|！=|j-b|，即|i-k|！=|j-pos[k]|
            if (Math.abs(i - k) == Math.abs(j - pos[k])) return false;//共斜线就不行
        }

        //所有的前面皇后查完，与i j位置不冲突，OK
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

手撕N皇后问题暴力递归代码，i行都摆不了，就需要i-1行调整去j+1列

上面的N皇后问题的摆法，宏观调度那一节，咱们说清楚了
咱们想在来到i行，要放在j位置，看看合法吗？
不合法，的话，需要i-1行那个皇后，去j+1位置尝试

主函数咋调用呢？
从0行开始放第一个皇后，N*N的棋盘，合法的摆法是多少？
调用：f(N, pos, 0)

手撕代码：

//**f（n,i,pos）**：填写n皇后棋盘，0--i-1行都放好了，合格的，
    // 请你在第i行放皇后，让放的i行j列不跟0--i-1行所有皇后的位置冲突，得到的合法的摆法是多少？
    // 同时，把i行的j列放入pos记录好。
    public static int f(int N, int[] pos, int i){
        //（2）如果能顺利填下去，知道i=N=9了，那刚刚这一路摆法就是合格的一条路径，返回1种合法的方法
        if (i == N) return 1;

        //（1）每一行中，j从0--N-1都看一遍，看看能否放下？
        int ans = 0;
        for (int j = 0; j < N; j++) {
            //j不行，往j+1放，很容易理解
            if (isOK(pos, i, j)){
                pos[i] = j;//i行的放j列OK？记录一下
                //然然避免i行冲突，直接去i+1行看看，有多少种摆法，回来累加到ans上
                ans += f(N, pos, i +1);
            }
        }//ans +=的目的是（3）然后再尝试**i**行，去**j+1**列试试，有没有新的可能呢？
        // 有就把方法数累加到ans结果上，最后返回。

        return ans;//这个暴力递归收集了所有可能的i行的摆法，累加起来。
    }
    //主函数调用
    public static int nHuangHouPro(int N){
        if (N <= 0) return 0;

        //生成pos数组，便于放i行j列那个皇后记录一下
        int[] pos = new int[N];

        return f(N, pos, 0);//从0行开始放第一个皇后，N*N的棋盘，合法的摆法是多少？
    }

    public static void test(){
        int N = 9;
        System.out.println(nHuangHou(N));
        System.out.println(nHuangHouPro(N));
    }

    public static void main(String[] args) {
        test();
    }
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

测试一波：

352
352
1
2

没得问题！
这就是N皇后问题的最优解！！！

咱们来试试暴力递归改写动态规划的代码

先呢，N固定，pos可以变动，但是i就一个变量，这有点像是，一个变量从左往右的尝试模型！！！
那咱们这么定义：
f(int N, int[] pos, int i)
dp[i]就是从i–N-1上放皇后有多少种摆法?

根据暴力递归改这个代码，填表！
由于咱们的pos需要记录0–i-1行的所有皇后问题
咱就不能直接从右往左填表，因为依赖超前了，这个填表是不行的
放弃！

上面的最优解了解了就行。

---

总结

提示：重要经验：

1）N皇后问题，主要在宏观调度过程中，知道i行不能放，就要让i-1行去j+1列尝试新的可能性
2）另外，合法的N皇后在想放在ij处的话，要与所有0–i-1行的皇后们要不共列，不共斜线，那个不共斜线的条件就是2个直角边不能相等。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。