Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
tag:
java
public void solveSudoku(char[][] board) {
solve(board, 0);
}
//dfs
public boolean solve(char[][] board, int k) {
if(k>=81) {
return true;
} else {
int i=k/9, j=k%9;
if(board[i][j]!='.') {
return solve(board, k+1);
} else {
for(char c='1'; c<='9'; c++) {
board[i][j] = c;
if(isValid(board, i,j) && solve(board, k+1)) {
return true;
}
board[i][j] = '.';
}
}
}
return false;
}
//ref: [36. Valid Sudoku](https://leetcode.com/problems/valid-sudoku/)
public boolean isValid(char[][] board, int x, int y) {
for(int i=0; i<9; i++) {
if( (i!=y && board[x][i]==board[x][y]) || (i!=x && board[i][y]==board[x][y]) || ( (x!=3*(x/3)+i/3) && (y!=3*(y/3)+i%3) && board[3*(x/3)+i/3][3*(y/3)+i%3]==board[x][y])) {
return false;
}
}
return true;
}
go