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 another backtracking problem. The key point is, when r > 8 (the whole thing is filled), the function returns a true, which will terminate the whole recursion. Very Important! Another thing is that if you searched a pre-filled location, directly return the result of the next position, do not continue the procedure.

public class Solution {
public void solveSudoku(char[][] board) {
if (solvable (board, 0, 0))
return;
}
public boolean solvable (char[][] board, int r, int c) {
if (r > 8) //filled eveything
return true;
int nextR = (c == 8)? r+1 : r;
int nextC = (c == 8)? 0 : c+1;
if (board[r][c] == '.') {
for (int i = 1; i <= 9; i++) {// try 1 ~ 9
board[r][c] = (char)(i + (int)'0');
if (isValid(board, r, c))
if (solvable(board, nextR, nextC))
return true;
}
board[r][c] = '.';
return false;
}
return solvable(board, nextR, nextC);
}
public boolean isValid(char[][] board, int r, int c) {
for (int i = 0; i < 9; i++) {
if (board[r][i] == board[r][c]) {
if (i != c)
return false;
}
if (board[i][c] == board[r][c]) {
if (i != r)
return false;
}
}
//get the starting point of the 3x3 square
int row = (r/3)*3;
int col = (c/3)*3;
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if (board[i][j] == board[r][c])
if (i != r || j != c)
return false;
}
}
return true;
}
}

### Like this:

Like Loading...

*Related*