2021-01-11经典的八皇后问题和N皇后问题, 回溯( 二 ) _皇后

}}
搞懂了上面的分析过程，那么这题的代码轮廓就呼之欲出了
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行为什么要复制一份，因为数组是引用传递，这涉及到递归的时候分支污染问题（后面有时间我会专门写一篇关于递归的时候分支污染问题）。当然不复制一份也是可以的，我们下面再讲。当我们把上面的问题都搞懂的时候，代码也就很容易写出来了，我们来看下N皇后的最终代码
【2021-01-11经典的八皇后问题和N皇后问题, 回溯】 1public void solveNQueens(int n) {2char[][] chess = new char[n][n];3for (int i = 0; i < n; i++)4for (int j = 0; j < n; j++)5chess[i][j] = '.';6solve(chess, 0);7}89private void solve(char[][] chess, int row) {10if (row == chess.length) {11//自己写的一个公共方法，打印二维数组的，12// 主要用于测试数据用的13Util.printTwoCharArrays(chess);14System.out.println();15return;16}17for (int col = 0; col < chess.length; col++) {18if (valid(chess, row, col)) {19char[][] temp = copy(chess);20temp[row][col] = 'Q';21solve(temp, row + 1);22}23}24}2526//把二维数组chess中的数据测下copy一份27private char[][] copy(char[][] chess) {28char[][] temp = new char[chess.length][chess[0].length];29for (int i = 0; i < chess.length; i++) {30for (int j = 0; j < chess[0].length; j++) {31temp[i][j] = chess[i][j];32}33}34return temp;35}3637//row表示第几行，col表示第几列38private boolean valid(char[][] chess, int row, int col) {39//判断当前列有没有皇后,因为他是一行一行往下走的，40//我们只需要检查走过的行数即可，通俗一点就是判断当前41//坐标位置的上面有没有皇后42for (int i = 0; i < row; i++) {43if (chess[i][col] == 'Q') {44return false;45}46}47//判断当前坐标的右上角有没有皇后48for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {49if (chess[i][j] == 'Q') {50return false;51}52}53//判断当前坐标的左上角有没有皇后54for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {55if (chess[i][j] == 'Q') {56return false;57}58}59return true;60}
代码看起来比较多，我们主要看下solve方法即可，其他的方法不看也可以，知道有这个功能就行。solve代码中其核心代码是在17-23行，上面是终止条件的判断，我们就用4皇后来测试一下
solveNQueens(4);
看一下打印的结果
我们看到4皇后的时候有两组解，其中第一组和我们上面图中分析的完全一样。
4皇后解决了，那么8皇后也一样，我们只要在函数调用的时候传入8就可以了。同理，要想计算10皇后，20皇后，100皇后……也都是可以的。
回溯解决
上面代码中每次遇到能放皇后的时候，我们都会把原数组复制一份，这样对新数据的修改就不会影响到原来的，也就是不会造成分支污染。但这样每次尝试的时候都都把原数组复制一份，影响效率，有没有其他的方法不复制呢，是有的。就是每次我们选择把这个位置放置皇后的时候，如果最终不能成功，那么返回的时候我们就还要把这个位置还原。这就是回溯算法，也是试探算法。我们来看下代码