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.
This is a simple problem on dfs method
public class Solution {
public void solveSudoku(char[][] board){
List<Integer> blankCells = new ArrayList<Integer>();
//a sudoku board is a 9 by 9 array
for(int i = 0; i < 81; ++i){
if(board[i / 9][ i % 9 ] == '.')
blankCells.add(i);
}
dfs(board, 0, blankCells);
}
private boolean dfs(char[][] board, int start, List<Integer> blankCells) {
if(start == blankCells.size()) return true; //dfs reaches the end
//get the coordinates of the cell to be filled
int currentCoordinate = blankCells.get(start);
int row = currentCoordinate / 9;
int column = currentCoordinate % 9;
//fill a number in the cell
for(int num = 1; num < 10; ++num) {
//check the sudoku is valid after being filled num
if(isValid(num, board,row,column)) {
board[row][column] = (char)(num + '0');
if(dfs(board,start + 1, blankCells))
return true;
//if a solution can not be reached after the filling, we need to erase the filling for next try
board[row][column] = '.';
}
}
return false;
}
private boolean isValid(int num, char[][] board, int row, int column) {
//check whether num is in the row, column and grid
for(int i = 0; i < 9; ++i){
if(board[row][i] -'0' == num) return false; //row
if(board[i][column] - '0' == num) return false; //column
if(board[3 *(row / 3) + i / 3][3 * (column / 3) + i % 3] - '0' == num) return false;
}
return true;
}
}