content: package question0037_sudoku_solver;
  
  import java.util.ArrayList;
  import java.util.List;
  
  /**
   * https://leetcode-cn.com/problems/sudoku-solver/
   *
   * 回溯法。
   *
   * 执行用时：9ms，击败64.47%。消耗内存：35.4MB，击败70.78%。
   */
  public class Solution {
      private List<Integer> list = new ArrayList<>();
  
      public void solveSudoku(char[][] board) {
          for (int i = 0; i < 9; i++) {
              for (int j = 0; j < 9; j++) {
                  if (board[i][j] == '.') {
                      list.add(i * 10 + j);
                  }
              }
          }
          try {
              fillNumber(board, 0);
          } catch (Exception e) {}
      }
  
      private void fillNumber(char[][] board, int index) {
          if (index == list.size()) {
              throw new RuntimeException();   //利用异常来跳出该函数
          }
          int i = list.get(index) / 10, j = list.get(index) % 10;
          for (int num = 1; num <= 9; num++) {
              if (canFillThisNum(board, i, j, num)) {
                  board[i][j] = (char) (num + '0');
                  fillNumber(board, index + 1);
                  board[i][j] = '.';  //变量的回溯
              }
          }
      }
  
      private boolean canFillThisNum(char[][] board, int x, int y, int num) {
          if (board[x][y] != '.') {
              return false;
          }
          for (int k = 0; k < 9; k++) {
              if (num == board[x][k] - '0') {
                  return false;
              }
              if (num == board[k][y] - '0') {
                  return false;
              }
          }
          int top = (x / 3) * 3, bottom = top + 2, left = (y / 3) * 3, right = left + 2;
          for (int i = top; i <= bottom; i++) {
              for (int j = left; j <= right; j++) {
                  if (num == board[i][j] - '0') {
                      return false;
                  }
              }
          }
          return true;
      }
  }