Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9
must occur exactly once in each row. - Each of the digits
1-9
must occur exactly once in each column. - Each of the the digits
1-9
must occur exactly once in each of the 93x3
sub-boxes of the grid.
Empty cells are indicated by the character '.'
.
A sudoku puzzle…
…and its solution numbers marked in red.
Note:
- The given board contain only digits
1-9
and the character'.'
. - You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always
9x9
.
Solution 1:
class Solution {
public void solveSudoku(char[][] board) {
helper(board);
}
public boolean helper(char[][] board){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]!='.'){
continue;
}
for(char k='1';k<='9';k++){
if(isValid(board, i, j, k)){
board[i][j] = k;
if (helper(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public boolean isValid(char[][] board, int row, int column, char k){
for(int i=0;i<9;i++){
if(board[row][i]!='.' && board[row][i]==k) return false;
if(board[i][column]!='.' && board[i][column]==k) return false;
if(board[3 * (row / 3) + i / 3][3 * (column / 3) + i % 3]!='.' && board[3 * (row / 3) + i / 3][3 * (column / 3) + i % 3]== k) return false;
}
return true;
}
}