这题经典dfs了,都能背下来[s:ac:茶]
class Solution {
public void solveSudoku(char[][] board) {
dfs(board, 0);
}
boolean check(int i, int j, char[][] board, int target) {
for (int k=0; k<9; k++) {if (board[i][k] - '0' == target) {return false;}}
for (int k=0; k<9; k++) {if (board[k][j] - '0' == target) {return false;}}
for (int a=0; a<3; a++) {
for (int b=0; b<3; b++) {if (board[(i/3)*3+a][(j/3)*3+b] - '0' == target) {return false;}}
}
return true;
}
boolean dfs(char[][] board, int index) {
if (index < 81) {
int i = index/9; int j = index%9;
if (board[i][j] != '.') {return dfs(board, index+1);}
for (int k=1; k<10; k++) {
if (check(i, j, board, k)) {
board[i][j] = (char) (k+'0');
if (dfs(board, index+1)) {return true;}
else {board[i][j] = '.';}
}
}
return false;
}
return true;
}
}
input:[["3",".",".","1",".",".","4",".","."],["6","7",".",".",".","3","8",".","."],[".",".",".",".",".","2",".","9","."],[".","5",".",".","4",".",".","2","."],[".",".",".",".","1",".",".",".","."],[".","6",".",".","3",".",".","1","."],[".","9",".","5",".",".",".",".","."],[".",".","7","6",".",".",".","4","8"],[".",".","4",".",".","9",".",".","7"]]
output:[["3","2","9","1","5","8","4","7","6"],["6","7","1","4","9","3","8","5","2"],["4","8","5","7","6","2","1","9","3"],["1","5","3","8","4","7","6","2","9"],["7","4","2","9","1","6","3","8","5"],["9","6","8","2","3","5","7","1","4"],["8","9","6","5","7","4","2","3","1"],["5","3","7","6","2","1","9","4","8"],["2","1","4","3","8","9","5","6","7"]]