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

1private void solve(char[][] chess, int row) {2if (row == chess.length) {3//自己写的一个公共方法，打印二维数组的，4// 主要用于测试数据用的5Util.printTwoCharArrays(chess);6System.out.println();7return;8}9for (int col = 0; col < chess.length; col++) {10if (valid(chess, row, col)) {11chess[row][col] = 'Q';12solve(chess, row + 1);13chess[row][col] = '.';14}15}16}
主要来看下11-13行，其他的都没变，还和上面的一样。这和我们之前讲的391，回溯算法求组合问题很类似。他是先假设[row][col]这个位置可以放皇后，然后往下找，无论找到找不到最后都会回到这个地方，因为这里是递归调用，回到这个地方的时候我们再把它复原，然后走下一个分支。最后我们再来看下使用回溯算法解N皇后的完整代码
public void 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] = '.';solve(chess, 0);}private void solve(char[][] chess, int row) {if (row == chess.length) {//自己写的一个公共方法，打印二维数组的，// 主要用于测试数据用的Util.printTwoCharArrays(chess);System.out.println();return;}for (int col = 0; col < chess.length; col++) {if (valid(chess, row, col)) {chess[row][col] = 'Q';solve(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;}
总结
8皇后问题其实是一道很经典的回溯算法题，我们这里并没有专门针对8皇后来讲，我们这里讲的是N皇后，如果这道题搞懂了，那么8皇后自然也就懂了，因为这里的N可以是任何正整数。
递归一般可能会有多个分支，我们要保证每个分支的修改不会污染其他分支，也就是不要对其他分支造成影响，这一点很重要。由于一些语言中除了基本类型以外，其他的大部分都是引用传递，所以我们在一个分支修改之后可能就会对其他分支产生一些我们不想要的垃圾数据，这个时候我们就有两中解决方式，一种就是我们上面讲到的第一种，复制一份新的数据，这样每个分支都会产生一些新的数据，所以即使修改了也不会对其他分支有影响。还一种方式就是我们每次使用完之后再把它复原，一般的情况下我们都会选择第二种，因为这种代码更简洁一些，也不会重复的复制数据，造成大量的垃圾数据。
转自：#