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.
A sudoku puzzle...
...and its solution numbers marked in red.
Solution:
DFS transformation.
Solution:
DFS transformation.
public 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] == '.'){
for(int k = 1; k <= 9; k++){
board[i][j] = (char)(k + '0');
if(isValid(board, i, j) && helper(board))
return true;
board[i][j] = '.';
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int row, int col){
char c = board[row][col];
for(int i = 0; i < 9; i++){ // check rows
if(i == row) continue;
if(board[i][col] == c) return false;
}
for(int j = 0; j < 9; j++){ // check cols
if(j == col) continue;
if(board[row][j] == c) return false;
}
int a = row/3*3;
int b = col/3*3;
for(int i = 0; i < 3; i++){ // check cubic
for(int j = 0; j < 3; j++){
if(a+i==row && b+j==col) continue;
if(board[a+i][b+j] == c) return false;
}
}
return true;
}
}
No comments:
Post a Comment