37. 解数独

https://www.programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html

  1. class Solution {
  2.     private boolean backtracking(char[][] board){
  3.         for (int i = 0; i < board.length; i++) {
  4.             for (int j = 0; j < board[0].length; j++) {
  5.                 if (board[i][j] != '.'){//如果数字，跳过
  6.                     continue;
  7.                 }
  8.                 for (char k = '1';k <= '9'; k++){
  9.                     if (isValid(i, j, k, board)){//如果合法
  10.                         board[i][j] = k;//放置元素
  11.                         if (backtracking(board)) return true;// 如果找到合适一组立刻返回
  12.                         board[i][j] = '.';//回溯，撤回元素
  13.                     }
  14.                 }
  15.                 //找完还没找到
  16.                 return false;// 9个数都试完了，都不行，那么就返回false
  17.             }
  18.         }
  19.         return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
  20.     }
  22.     //合法性判断
  23.     private boolean isValid(int row, int col, char val, char[][] board) {
  24.         //判断行
  25.         for (int i = 0; i < 9; i++) {
  26.             if (board[row][i] == val){
  27.                 return false;
  28.             }
  29.         }
  31.         //判断列
  32.         for (int j = 0; j < 9; j++) {
  33.             if (board[j][col] == val){
  34.                 return false;
  35.             }
  36.         }
  38.         //判断九宫格内 这里两层for嵌套
  39.         int startRow = (row / 3) * 3;
  40.         int startCol = (col / 3) * 3;
  41.         for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
  42.             for (int j = startCol; j < startCol + 3; j++) {
  43.                 if (board[i][j] == val ) {
  44.                     return false;
  45.                 }
  46.             }
  47.         }
  48.         return true;
  49.     }
  51.     public void solveSudoku(char[][] board) {
  52.         backtracking(board);
  53.     }
  54. }