LeetCode上有一道数独题，https://leetcode.com/problems/sudoku-solver/。问题就不再赘述了。笔者能想到的方法就是根据数独的规则，然后暴力搜索了。

一开始用了List Set等集合类来表示当前的数字使用情况，结果性能较差，把List Set等集合类换成int[][]实现，性能大大提高了（-_-!平时用集合类用习惯了没想到性能差这么多）。
然后再把一个打印的地方给去掉。做了这两个优化后，在LeetCode上的执行时间从70ms减少为7ms。
不过LeetCode的这道数独题目比较简单（虽然显示是Hard类型的题），基本上不用怎么优化，但是实际上如果数独的解比较多时，暴搜应该就不太容易出结果了。下面是LeetCode上AC的代码。

代码：

public class Solution {
    private static final char INVALID = '.';
    private static final int SUDOKU_SIZE = 9;
    private boolean isSolved = false;
 
    public void solveSudoku(char[][] board) {
       // rowStatus[i][j] == 1表示当前的数独中，第i行中，数字j已经被使用
       // colStatus[i][j] == 1表示当前的数独中，第i列中，数字j已经被使用
       // gridStatus[i][j] == 1表示当前的数独中，第i个九宫格中，数字j已经被使用（把一个数独的图分成9个九宫格，起始编号为0）
       int[][] rowStatus, colStatus, gridStatus;
      
       rowStatus = new int[SUDOKU_SIZE][SUDOKU_SIZE + 1];
       colStatus = new int[SUDOKU_SIZE][SUDOKU_SIZE + 1];
       gridStatus = new int[SUDOKU_SIZE][SUDOKU_SIZE + 1];
       for (int i = 0; i < SUDOKU_SIZE; ++i) {
           for (int j = 0; j < SUDOKU_SIZE; ++j) {
              if (board[i][j] != INVALID) {
                  rowStatus[i][board[i][j] - '0'] = 1;
                  colStatus[j][board[i][j] - '0'] = 1;
                  gridStatus[i / 3 * 3 + j / 3][board[i][j] - '0'] = 1;
              }
           }
       }
       solveSudoku(board, 0, 0, rowStatus, colStatus, gridStatus);
    }
 
    private void solveSudoku(char[][] board, int i, int j,
           int[][] rowStatus, int[][] colStatus,
           int[][] gridStatus) {
        if (board[i][j] == INVALID) {
           // 如果当前位置没有合法值，尝试找一个
           for (int k = 1; k <= SUDOKU_SIZE; ++k) {
               if (rowStatus[i][k] != 1
                      && colStatus[j][k] != 1
                      && gridStatus[i / 3 * 3 + j / 3][k] != 1) {
                  // k是个合法值，试一下
                  board[i][j] = (char)(k + '0');
                  rowStatus[i][k] = 1;
                  colStatus[j][k] = 1;
                  gridStatus[i / 3 * 3 + j / 3][k] = 1;
                  if (i == SUDOKU_SIZE - 1 && j == SUDOKU_SIZE - 1) {
                      // Find the solution.
                      isSolved = true;
                      return;
                   } else {
                      // 还没完事，继续往下搜索
                      if (j < SUDOKU_SIZE - 1) {
                          solveSudoku(board, i, j + 1, rowStatus, colStatus, gridStatus);
                      } else {
                          solveSudoku(board, i + 1, 0, rowStatus, colStatus, gridStatus);
                      }
                      if (isSolved) {
                         return;
                      } else {
                         // 还没找到解，恢复一下现场，继续搜索
                         board[i][j] = INVALID;
                         rowStatus[i][k] = 0;
                         colStatus[j][k] = 0;
                         gridStatus[i / 3 * 3 + j / 3][k] = 0;
                      }
                   }
               }
           }
        } else {
            if (i == SUDOKU_SIZE - 1 && j == SUDOKU_SIZE - 1) {
               // Find the solution.
               isSolved = true;
               return;
            } else {
               // 继续搜索
               if (j < SUDOKU_SIZE - 1) {
                   solveSudoku(board, i, j + 1, rowStatus, colStatus, gridStatus);
               } else {
                   solveSudoku(board, i + 1, 0, rowStatus, colStatus, gridStatus);
               }
            }
        }
    }
   
    public static void main(String[] args) {
       Solution solution = new Solution();
       char[][] board = new char[][] {
           {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
           {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
           {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
           {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
           {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
           {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
           {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
           {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
           {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
       };
       solution.solveSudoku(board);
    }
}