【数据结构和算法】N皇后，回溯算法图文详解

之前在公众号写过和这题类似的的，有兴趣的也可以看下394，经典的八皇后问题和N皇后问题

1，4皇后问题，递归解决

我们来找规律，先看一下4皇后的问题

比如在下面的4*4的格子里，如果我们在其中一个格子里输入了皇后，那么在这一行这一列和这左右两边的对角线上都不能有皇后。

所以有一种方式就是我们一个个去试

第一行

比如我们在第一行第一列输入了一个皇后

第二行

第二行我们就不能在第一列和第二列输入皇后了，因为有冲突了。但我们可以在第3列输入皇后

第三行

第三行我们发现在任何位置输入都会有冲突。这说明我们之前选择的是错误的，再回到上一步，我们发现第二步不光能选择第3列，而且还能选择第4列，既然选择第3列不合适，那我们就选择第4列吧

第二行（重新选择）

第二行我们选择第4列

第三行（重新选择）

第3行我们只有选择第2列不会有冲突

第四行

我们发现第4行又没有可选择的了。第一次重试失败

第二次重试

到这里我们只有重新回到第一步了，这说明我们之前第一行选择第一列是无解的，所以我们第一行不应该选择第一列，我们再来选择第二列来试试

第一行

这一行我们选择第2列

第二行

第二行我们前3个都不能选，只能选第4列

第三行

第三行我们只能选第1列

第四行

第四行我们只能选第3列 最后我们终于找到了一组解。除了这组解还有没有其他解呢，肯定还是有的，因为4皇后是有两组解的，这里我们就不在一个个试了。

我们来看一下他查找的过程，就是先从第1行的第1列开始往下找，然后再从第1行的第2列……，一直到第1行的第n列。代码该怎么写呢，看到这里估计大家都已经想到了，这不就是一棵N叉树的前序遍历吗，我们来看下，是不是下面这样的。 我们先来看一下二叉树的前序遍历怎么写，不明白的可以参考下373，数据结构-6,树

public static void preOrder(TreeNode tree) {
    if (tree == null)
        return;
    System.out.printf(tree.val + "");
    preOrder(tree.left);
    preOrder(tree.right);
}

二叉树是有两个子节点，那么N叉树当然是有N个子节点了，所以N叉树的前序遍历是这样的

public static void preOrder(TreeNode tree) {
    if (tree == null)
        return;
    System.out.printf(tree.val + "");
    preOrder("第1个子节点");
    preOrder("第2个子节点");
    ……
    preOrder("第n个子节点");
}

如果N是一个很大的值，这样写要写死人了，我们一般使用循环的方式

public static void preOrder(TreeNode tree) {
    if (tree == null)
        return;
    System.out.printf(tree.val + "");
    for (int i = 0; i <n ; i++) { preorder("第i个子节点"); } ``` 搞懂了上面的分析过程，那么这题的代码轮廓就呼之欲出了 private void solve(char[][] chess, int row) "终止条件" return; for (int col < chess.length; col++) 判断这个位置是否可以放皇后 if (valid(chess, row, col)) 如果可以放，我们就把原来的数组chess复制一份， char[][] temp="copy(chess);" 然后在这个位置放上皇后 temp[row][col]="Q" 下一行 solve(temp, row + 1); 我们来分析下上面的代码，因为是递归所以必须要有终止条件，那么这题的终止条件就是我们最后一行已经走完了，也就是 (row="=" chess.length) 第7行就是判断在这个位置我们能不能放皇后，如果不能放我们就判断这一行的下一列能不能放……，如果能放我们就把原来数组chess复制一份，然后把皇后放到这个位置，然后再判断下一行，这和我们上面画图的过程非常类似。注意这里的第9行为什么要复制一份，因为数组是引用传递，这涉及到递归的时候分支污染问题，关于分支污染可以看下[426，什么是递归，通过这篇文章，让你彻底搞懂递归](https: mp.weixin.qq.com s?__biz="MzU0ODMyNDk0Mw==&amp;mid=2247487910&amp;idx=1&amp;sn=2670aec7139c6b98e83ff66114ac1cf7&amp;chksm=fb418286cc360b90741ed54fecd62fd45571b2caba3e41473a7ea0934f918d4b31537689c664&amp;token=1327182919&amp;lang=zh_CN#rd)，当然不复制一份也是可以的，我们下面再讲。当我们把上面的问题都搞懂的时候，代码也就很容易写出来了。" ```java public list<list<string>&gt; solveNQueens(int n) {
        char[][] chess = new char[n][n];
        //初始化数组
        for (int i = 0; i &lt; n; i++)
            for (int j = 0; j &lt; n; j++)
                chess[i][j] = '.';
        List<list<string>&gt; res = new ArrayList&lt;&gt;();
        solve(res, chess, 0);
        return res;
    }

    private void solve(List<list<string>&gt; res, char[][] chess, int row) {
        //终止条件，最后一行都走完了，说明找到了一组，把它加入到集合res中
        if (row == chess.length) {
            res.add(construct(chess));
            return;
        }
        //遍历每一行
        for (int col = 0; col &lt; chess.length; col++) {
            //判断这个位置是否可以放皇后
            if (valid(chess, row, col)) {
                //数组复制一份
                char[][] temp = copy(chess);
                //在当前位置放个皇后
                temp[row][col] = 'Q';
                //递归到下一行继续
                solve(res, temp, row + 1);
            }
        }
    }

    //把二维数组chess中的数据测下copy一份
    private char[][] copy(char[][] chess) {
        char[][] temp = new char[chess.length][chess[0].length];
        for (int i = 0; i &lt; chess.length; i++) {
            for (int j = 0; j &lt; chess[0].length; j++) {
                temp[i][j] = chess[i][j];
            }
        }
        return temp;
    }

    //row表示第几行，col表示第几列
    private boolean valid(char[][] chess, int row, int col) {
        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可，通俗一点就是判断当前
        //坐标位置的上面有没有皇后
        for (int i = 0; i &lt; row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }
        //判断当前坐标的右上角有没有皇后
        for (int i = row - 1, j = col + 1; i &gt;= 0 &amp;&amp; j &lt; chess.length; i--, j++) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        //判断当前坐标的左上角有没有皇后
        for (int i = row - 1, j = col - 1; i &gt;= 0 &amp;&amp; j &gt;= 0; i--, j--) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    //把数组转为list
    private List<string> construct(char[][] chess) {
        List<string> path = new ArrayList&lt;&gt;();
        for (int i = 0; i &lt; chess.length; i++) {
            path.add(new String(chess[i]));
        }
        return path;
    }

而这题让求的是n皇后的个数，不是让打印出来，我们修改一下，直接返回最终的个数，代码如下

    public int Nqueen (int n) {
      return solveNQueens(n).size();
    }


public List<list<string>&gt; solveNQueens(int n) {
    char[][] chess = new char[n][n];
    //初始化数组
    for (int i = 0; i &lt; n; i++)
        for (int j = 0; j &lt; n; j++)
            chess[i][j] = '.';
    List<list<string>&gt; res = new ArrayList&lt;&gt;();
    solve(res, chess, 0);
    return res;
}
 
private void solve(List<list<string>&gt; res, char[][] chess, int row) {
    //终止条件，最后一行都走完了，说明找到了一组，把它加入到集合res中
    if (row == chess.length) {
        res.add(construct(chess));
        return;
    }
    //遍历每一行
    for (int col = 0; col &lt; chess.length; col++) {
        //判断这个位置是否可以放皇后
        if (valid(chess, row, col)) {
            //数组复制一份
            char[][] temp = copy(chess);
            //在当前位置放个皇后
            temp[row][col] = 'Q';
            //递归到下一行继续
            solve(res, temp, row + 1);
        }
    }
}
 
//把二维数组chess中的数据测下copy一份
private char[][] copy(char[][] chess) {
    char[][] temp = new char[chess.length][chess[0].length];
    for (int i = 0; i &lt; chess.length; i++) {
        for (int j = 0; j &lt; chess[0].length; j++) {
            temp[i][j] = chess[i][j];
        }
    }
    return temp;
}
 
//row表示第几行，col表示第几列
private boolean valid(char[][] chess, int row, int col) {
    //判断当前列有没有皇后,因为他是一行一行往下走的，
    //我们只需要检查走过的行数即可，通俗一点就是判断当前
    //坐标位置的上面有没有皇后
    for (int i = 0; i &lt; row; i++) {
        if (chess[i][col] == 'Q') {
            return false;
        }
    }
    //判断当前坐标的右上角有没有皇后
    for (int i = row - 1, j = col + 1; i &gt;= 0 &amp;&amp; j &lt; chess.length; i--, j++) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }
    //判断当前坐标的左上角有没有皇后
    for (int i = row - 1, j = col - 1; i &gt;= 0 &amp;&amp; j &gt;= 0; i--, j--) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
 
//把数组转为list
private List<string> construct(char[][] chess) {
    List<string> path = new ArrayList&lt;&gt;();
    for (int i = 0; i &lt; chess.length; i++) {
        path.add(new String(chess[i]));
    }
    return path;
}

看一下运行结果，我们看到运行效率很差，这是因为我们不停的复制数组

2，回溯解决

上面代码中每次遇到能放皇后的时候，我们都会把原数组复制一份，这样对新数据的修改就不会影响到原来的，也就是不会造成分支污染。但这样每次尝试的时候都都把原数组复制一份，影响效率，有没有其他的方法不复制呢，是有的。就是每次我们选择把这个位置放置皇后的时候，如果最终不能成功，那么返回的时候我们就还要把这个位置还原。这就是回溯算法，也是试探算法。我们来看下代码

    private void solve(List<list<string>&gt; res, char[][] chess, int row) {
        if (row == chess.length) {
            res.add(construct(chess));
            return;
        }
        for (int col = 0; col &lt; chess.length; col++) {
            if (valid(chess, row, col)) {
                chess[row][col] = 'Q';
                solve(res, chess, row + 1);
                chess[row][col] = '.';
            }
        }
    }

主要来看下8-10行，其他的都没变，还和上面的一样。这和之前讲的391，回溯算法求组合问题很类似。他是先假设[row][col]这个位置可以放皇后，然后往下找，无论找到找不到最后都会回到这个地方，因为这里是递归调用，回到这个地方的时候再把它复原，然后走下一个分支。最后再来看下使用回溯算法解N皇后的完整代码

    public int Nqueen (int n) {
      return solveNQueens(n).size();
    }

    public List<list<string>&gt; solveNQueens(int n) {
        char[][] chess = new char[n][n];
        for (int i = 0; i &lt; n; i++)
            for (int j = 0; j &lt; n; j++)
                chess[i][j] = '.';
        List<list<string>&gt; res = new ArrayList&lt;&gt;();
        solve(res, chess, 0);
        return res;
    }

    private void solve(List<list<string>&gt; res, char[][] chess, int row) {
        if (row == chess.length) {
            res.add(construct(chess));
            return;
        }
        for (int col = 0; col &lt; chess.length; col++) {
            if (valid(chess, row, col)) {
                chess[row][col] = 'Q';
                solve(res, chess, row + 1);
                chess[row][col] = '.';
            }
        }
    }

    //row表示第几行，col表示第几列
    private boolean valid(char[][] chess, int row, int col) {
        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可，通俗一点就是判断当前
        //坐标位置的上面有没有皇后
        for (int i = 0; i &lt; row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }
        //判断当前坐标的右上角有没有皇后
        for (int i = row - 1, j = col + 1; i &gt;= 0 &amp;&amp; j &lt; chess.length; i--, j++) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        //判断当前坐标的左上角有没有皇后
        for (int i = row - 1, j = col - 1; i &gt;= 0 &amp;&amp; j &gt;= 0; i--, j--) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    //把数组转为list
    private List<string> construct(char[][] chess) {
        List<string> path = new ArrayList&lt;&gt;();
        for (int i = 0; i &lt; chess.length; i++) {
            path.add(new String(chess[i]));
        }
        return path;
    }

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解