之前在公众号写过和这题类似的的,有兴趣的也可以看下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 = 0; col < chess.length; col++) { //判断这个位置是否可以放皇后 if (valid(chess, row, col)) { //如果可以放,我们就把原来的数组chess复制一份, char[][] temp = copy(chess); //然后在这个位置放上皇后 temp[row][col] = 'Q'; //下一行 solve(temp, row + 1); } } }
我们来分析下上面的代码,因为是递归所以必须要有终止条件,那么这题的终止条件就是我们最后一行已经走完了,也就是
if (row == chess.length) { return; }
第7行就是判断在这个位置我们能不能放皇后,如果不能放我们就判断这一行的下一列能不能放……,如果能放我们就把原来数组chess复制一份,然后把皇后放到这个位置,然后再判断下一行,这和我们上面画图的过程非常类似。注意这里的第9行为什么要复制一份,因为数组是引用传递,这涉及到递归的时候分支污染问题,关于分支污染可以看下426,什么是递归,通过这篇文章,让你彻底搞懂递归,当然不复制一份也是可以的,我们下面再讲。当我们把上面的问题都搞懂的时候,代码也就很容易写出来了。
public List<List<String>> solveNQueens(int n) { char[][] chess = new char[n][n]; //初始化数组 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) chess[i][j] = '.'; List<List<String>> res = new ArrayList<>(); solve(res, chess, 0); return res; } private void solve(List<List<String>> res, char[][] chess, int row) { //终止条件,最后一行都走完了,说明找到了一组,把它加入到集合res中 if (row == chess.length) { res.add(construct(chess)); return; } //遍历每一行 for (int col = 0; col < 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 < chess.length; i++) { for (int j = 0; j < 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 < row; i++) { if (chess[i][col] == 'Q') { return false; } } //判断当前坐标的右上角有没有皇后 for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) { if (chess[i][j] == 'Q') { return false; } } //判断当前坐标的左上角有没有皇后 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chess[i][j] == 'Q') { return false; } } return true; } //把数组转为list private List<String> construct(char[][] chess) { List<String> path = new ArrayList<>(); for (int i = 0; i < 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>> solveNQueens(int n) { char[][] chess = new char[n][n]; //初始化数组 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) chess[i][j] = '.'; List<List<String>> res = new ArrayList<>(); solve(res, chess, 0); return res; } private void solve(List<List<String>> res, char[][] chess, int row) { //终止条件,最后一行都走完了,说明找到了一组,把它加入到集合res中 if (row == chess.length) { res.add(construct(chess)); return; } //遍历每一行 for (int col = 0; col < 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 < chess.length; i++) { for (int j = 0; j < 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 < row; i++) { if (chess[i][col] == 'Q') { return false; } } //判断当前坐标的右上角有没有皇后 for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) { if (chess[i][j] == 'Q') { return false; } } //判断当前坐标的左上角有没有皇后 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chess[i][j] == 'Q') { return false; } } return true; } //把数组转为list private List<String> construct(char[][] chess) { List<String> path = new ArrayList<>(); for (int i = 0; i < chess.length; i++) { path.add(new String(chess[i])); } return path; }
看一下运行结果,我们看到运行效率很差,这是因为我们不停的复制数组
2,回溯解决
上面代码中每次遇到能放皇后的时候,我们都会把原数组复制一份,这样对新数据的修改就不会影响到原来的,也就是不会造成分支污染。但这样每次尝试的时候都都把原数组复制一份,影响效率,有没有其他的方法不复制呢,是有的。就是每次我们选择把这个位置放置皇后的时候,如果最终不能成功,那么返回的时候我们就还要把这个位置还原。这就是回溯算法,也是试探算法。我们来看下代码
private void solve(List<List<String>> res, char[][] chess, int row) { if (row == chess.length) { res.add(construct(chess)); return; } for (int col = 0; col < 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>> solveNQueens(int n) { char[][] chess = new char[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) chess[i][j] = '.'; List<List<String>> res = new ArrayList<>(); solve(res, chess, 0); return res; } private void solve(List<List<String>> res, char[][] chess, int row) { if (row == chess.length) { res.add(construct(chess)); return; } for (int col = 0; col < 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 < row; i++) { if (chess[i][col] == 'Q') { return false; } } //判断当前坐标的右上角有没有皇后 for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) { if (chess[i][j] == 'Q') { return false; } } //判断当前坐标的左上角有没有皇后 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chess[i][j] == 'Q') { return false; } } return true; } //把数组转为list private List<String> construct(char[][] chess) { List<String> path = new ArrayList<>(); for (int i = 0; i < chess.length; i++) { path.add(new String(chess[i])); } return path; }
我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666