51. N 皇后

  • java的字符串不太好用，需要注意很多细节

    1. class Solution {
    2.   List<List<String>> res = new ArrayList<>();
    3.   public List<List<String>> solveNQueens(int n) {
    4.       char[][] chessboard = new char[n][n];
    5.       for (char[] row : chessboard) {
    6.           Arrays.fill(row, '.');
    7.       }
    8.       backtrack(n, 0, chessboard);
    9.       return res;
    10.   }
    12.   public void backtrack(int n, int row, char[][] chessboard) {
    13.       if (row == n) {
    14.           res.add(Array2List(chessboard));
    15.           return;
    16.       }
    17.       for (int col = 0; col < n; ++col) {
    18.           if (isValid(chessboard, row, col, n)) {
    19.               chessboard[row][col] = 'Q';
    20.               backtrack(n, row + 1, chessboard);
    21.               chessboard[row][col] = '.';
    22.           }
    23.       }
    25.   }
    27.   public List<String> Array2List(char[][] chessboard) {
    28.       List<String> list = new ArrayList<>();
    29.       for (char[] row : chessboard) {
    30.           list.add(new String(row));
    31.       }
    32.       return list;
    33.   }
    35.   public boolean isValid(char[][] chessboard, int row, int col, int n) {
    36.       // 检查列
    37.       for (int i=0; i<row; ++i) { // 相当于剪枝
    38.           if (chessboard[i][col] == 'Q') {
    39.               return false;
    40.           }
    41.       }
    43.       // 检查45度对角线
    44.       for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
    45.           if (chessboard[i][j] == 'Q') {
    46.               return false;
    47.           }
    48.       }
    50.       // 检查135度对角线
    51.       for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
    52.           if (chessboard[i][j] == 'Q') {
    53.               return false;
    54.           }
    55.       }
    56.       return true;
    57.   }
    58. }

    37. 解数独

  • return false;没有终止条件也不会因为填不满棋盘而无限递归下去

    1. class Solution {
    2.   public void solveSudoku(char[][] board) {
    3.       backtrack(board);
    4.   }
    6.   //选择一个符合条件的路径即可，则有返回值
    7.   public boolean backtrack(char[][] board) {
    8.       for (int i = 0; i < board.length; ++i) {
    9.           for (int j = 0; j < board[0].length; ++j) {
    10.               if (board[i][j] != '.') {
    11.                   continue;
    12.               }
    13.               for (char k = '1'; k <= '9'; ++k) {
    14.                   if (isValid(board, i, j, k)) {
    15.                       board[i][j] = k;
    16.                       if (backtrack(board)) {
    17.                           return true;
    18.                       }
    19.                       board[i][j] = '.';
    20.                   }
    21.               }
    22.               return false; //关键，9个数都不行，则直接数独无解
    23.           }
    24.       }
    25.       return true;
    26.   }
    28.   public boolean isValid(char[][] board, int row, int col, char val){
    29.       // 同行是否重复
    30.       for (int i = 0; i < 9; i++){
    31.           if (board[row][i] == val){
    32.               return false;
    33.           }
    34.       }
    35.       // 同列是否重复
    36.       for (int j = 0; j < 9; j++){
    37.           if (board[j][col] == val){
    38.               return false;
    39.           }
    40.       }
    41.       // 9宫格里是否重复
    42.       int startRow = (row / 3) * 3;
    43.       int startCol = (col / 3) * 3;
    44.       for (int i = startRow; i < startRow + 3; i++){
    45.           for (int j = startCol; j < startCol + 3; j++){
    46.               if (board[i][j] == val){
    47.                   return false;
    48.               }
    49.           }
    50.       }
    51.       return true;
    52.   }
    53. }