package com.wujunshen.algorithm.leetcode.backtracking;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 17:26<br>
 */
public class 解数独 {
  public void solveSudoku(char[][] board) {
    // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
    boolean[][] rowUsed = new boolean[9][10];
    boolean[][] colUsed = new boolean[9][10];
    boolean[][][] boxUsed = new boolean[3][3][10];
    // 初始化
    for (int row = 0; row < board.length; row++) {
      for (int col = 0; col < board[0].length; col++) {
        int num = board[row][col] - '0';
        if (1 <= num && num <= 9) {
          rowUsed[row][num] = true;
          colUsed[col][num] = true;
          boxUsed[row / 3][col / 3][num] = true;
        }
      }
    }
    // 递归尝试填充数组
    recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
  }

  private boolean recusiveSolveSudoku(
      char[][] board,
      boolean[][] rowUsed,
      boolean[][] colUsed,
      boolean[][][] boxUsed,
      int row,
      int col) {
    // 边界校验, 如果已经填充完成, 返回true, 表示一切结束
    if (col == board[0].length) {
      col = 0;
      row++;
      if (row == board.length) {
        return true;
      }
    }
    // 是空则尝试填充, 否则跳过继续尝试填充下一个位置
    if (board[row][col] == '.') {
      // 尝试填充1~9
      for (int num = 1; num <= 9; num++) {
        boolean canUsed =
            !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row / 3][col / 3][num]);
        if (canUsed) {
          rowUsed[row][num] = true;
          colUsed[col][num] = true;
          boxUsed[row / 3][col / 3][num] = true;

          board[row][col] = (char) ('0' + num);
          if (recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)) {
            return true;
          }
          board[row][col] = '.';

          rowUsed[row][num] = false;
          colUsed[col][num] = false;
          boxUsed[row / 3][col / 3][num] = false;
        }
      }
    } else {
      return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
    }
    return false;
  }
}