题目

类型：回溯

难度：困难

解数独 - 图1

解题思路

尝试填充，如果发现重复了，那么擦除重新进行新一轮的尝试，直到把整个数组填充完成。

1、数独首先行，列，还有 3*3 的方格内数字是 1~9 不能重复。

2、声明布尔数组，表明行列中某个数字是否被使用了， 被用过视为 true，没用过为 false。

3、初始化布尔数组，表明哪些数字已经被使用过了。

4、尝试去填充数组，只要行，列， 还有 3*3 的方格内 出现已经被使用过的数字，我们就不填充，否则尝试填充。

5、如果填充失败，那么我们需要回溯。将原来尝试填充的地方改回来。

递归直到数独被填充完成。

代码

  1. class Solution {
  2.     public void solveSudoku(char[][] board) {
  3.         // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
  4.         boolean[][] rowUsed = new boolean[9][10];
  5.         boolean[][] colUsed = new boolean[9][10];
  6.         boolean[][][] boxUsed = new boolean[3][3][10];
  7.         // 初始化
  8.         for(int row = 0; row < board.length; row++){
  9.             for(int col = 0; col < board[0].length; col++) {
  10.                 int num = board[row][col] - '0';
  11.                 if(1 <= num && num <= 9){
  12.                     rowUsed[row][num] = true;
  13.                     colUsed[col][num] = true;
  14.                     boxUsed[row/3][col/3][num] = true;
  15.                 }
  16.             }
  17.         }
  18.         // 递归尝试填充数组 
  19.         recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
  20.     }
  22.     private boolean recusiveSolveSudoku(char[][]board, boolean[][]rowUsed, boolean[][]colUsed, boolean[][][]boxUsed, int row, int col){
  23.         // 边界校验, 如果已经填充完成, 返回true, 表示一切结束
  24.         if(col == board[0].length){
  25.             col = 0;
  26.             row++;
  27.             if(row == board.length){
  28.                 return true;
  29.             }
  30.         }
  31.         // 是空则尝试填充, 否则跳过继续尝试填充下一个位置
  32.         if(board[row][col] == '.') {
  33.             // 尝试填充1~9
  34.             for(int num = 1; num <= 9; num++){
  35.                 boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row/3][col/3][num]);
  36.                 if(canUsed){
  37.                     rowUsed[row][num] = true;
  38.                     colUsed[col][num] = true;
  39.                     boxUsed[row/3][col/3][num] = true;
  41.                     board[row][col] = (char)('0' + num);
  42.                     if(recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)){
  43.                         return true;
  44.                     }
  45.                     board[row][col] = '.';
  47.                     rowUsed[row][num] = false;
  48.                     colUsed[col][num] = false;
  49.                     boxUsed[row/3][col/3][num] = false;
  50.                 }
  51.             }
  52.         } else {
  53.             return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
  54.         }
  55.         return false;
  56.     }
  57. }