51. N 皇后

https://www.programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E8%A1%A5%E5%85%85
image.png

  1. class Solution {
  2.     List<List<String>> result = new ArrayList<>();
  4.     private void backTracking(int n, int row, char[][] chessboard) {
  5.         //终止条件
  6.         if (row == n) {
  7.             result.add(Array2List(chessboard));
  8.         }
  9.         //单层搜索的逻辑:
  10.         //递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
  11.         for (int col = 0; col < n; col++) {
  12.             if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
  13.                 chessboard[row][col] = 'Q';//放置皇后
  14.                 backTracking(n, row + 1, chessboard);//递归
  15.                 chessboard[row][col] = '.';//回溯 将棋盘重置为.
  16.             }
  17.         }
  19.     }
  20.     public List<List<String>> solveNQueens(int n) {
  21.         //初始化棋盘，全部为...
  22.         char[][] chessboard = new char[n][n];
  23.         for (char[] c : chessboard) {
  24.             //'.' 表示空，'Q' 表示皇后，初始化空棋盘。
  25.             Arrays.fill(c, '.');
  26.         }
  27.         backTracking(n,0,chessboard);
  28.         return result;
  29.     }
  30.     public List Array2List(char[][] chessboard) {
  31.         List<String> list = new ArrayList<>();
  33.         for (char[] c : chessboard) {
  34.             list.add(String.copyValueOf(c));
  35.         }
  36.         return list;
  37.     }
  39.     /**
  40.      * 校验
  41.      * 不能同行
  42.      * 不能同列
  43.      * 不能同斜线 （45度和135度角）
  44.      *
  45.      * @param row
  46.      * @param col
  47.      * @param chessboard
  48.      * @param n
  49.      * @return
  50.      */
  51.     private boolean isValid(int row, int col, char[][] chessboard, int n) {
  52.         //检验列
  53.         for (int i = 0; i < row; i++) {
  54.             if (chessboard[i][col] == 'Q') {
  55.                 return false;
  56.             }
  57.         }
  58.         //检查45°是否有皇后
  59.         for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
  60.             if (chessboard[i][j] == 'Q') {
  61.                 return false;
  62.             }
  63.         }
  64.         //检查135°
  65.         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
  66.             if (chessboard[i][j] == 'Q') {
  67.                 return false;
  68.             }
  69.         }
  70.         return true;
  71.     }
  73. }