☆☆☆☆☆思路：与N皇后问题类似。
class Solution { public void solveSudoku(char[][] board) { if (board == null || board.length == 0) return; dfs(board); } private boolean dfs(char[][] board) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { if (board[i][j] == '.') { // (i, j) 这个位置放c是否合适 for (char c = '1'; c <= '9'; c++) { if (isValid(board, i, j, c)) { board[i][j] = c; if (dfs(board)) { // 接着递归判断剩余空格是否也可以满足 return true; } board[i][j] = '.'; // 否则就回溯，撤销重新选择 } } return false; // 9个数都试完了，都不行，那么就返回false } } } return true; // 遍历完没有返回false，说明找到了合适棋盘位置了 } private boolean isValid(char[][] board, int i, int j, char c) { for (int k = 0; k < 9; k++) { if (board[i][k] == c) return false; // 检查行 if (board[k][j] == c) return false; // 检查列 // 检查 3*3 的单元格 // 3*(i/3) 和 3*(j/3) 保证了每个坐标都从其所属的3*3block的左上角开始遍历 // k / 3 的取值为000,1111,222代表行 ; k % 3 的取值为 012,012,012代表列 if (board[3*(i/3) + k / 3][3*(j/3) + k % 3] == c) return false; } return true; } }