1. Problem
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. Below is a Sudoku puzzle and a solution to it.
2. Idea
Previously, we have worked on validating whether a Sudoku puzzle is valid (LeetCode – Valid Sudoku). This problem goes further to ask for a solution. If you have heard about N Queens Puzzle (a famous one is eight queens puzzle), you may find similarities between them, and adopt a similar solution from it to this one. Basically, we can make a DFSlike exploration, put in a possible character at each empty cell. Once we reach a cell where no character can fit without violating the Sudoku rules, we backtrack to its preceding cell and try next possible character. A solution is found after we have filled the board and encounter no conflict. The onepass algorithm for validating a puzzle as in LeetCode – Valid Sudoku can be used as a subroutine. But since we work on one cell at a time, applying and updating the checkers is incremental during the exploration process.
3. Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

package me.darrensunny.leetcode;
/**
* LeetCode – Sudoku Solver
* Created by Darren on 14413.
*/
public class SudokuSolver {
// rowChecker[i][j]=true: j appears in row i
private boolean[][] rowChecker = new boolean[9][9];
// columnChecker[i][j]=true: j appears in column i
private boolean[][] columnChecker = new boolean[9][9];
// gridChecker[i][j]=true: j appears in grid i
// numberring from left to right, then top to bottom
private boolean[][] gridChecker = new boolean[9][9];
// 416ms for 6 test cases
public void solveSudoku(char[][] board) {
// Collect existing information on the board, and update the three checkers
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == ‘.’) // Empty
continue;
int val = board[i][j] – ‘1’;
// Check for the corresponding row, column, and grid at the same time
if (rowChecker[i][val]  columnChecker[j][val]  gridChecker[i/3*3+j/3][val])
// Violate at least one rule already
return;
// Update the three checkers
rowChecker[i][val] = columnChecker[j][val] = gridChecker[i/3*3+j/3][val] = true;
}
}
// Recursively solve Sudoku starting with board[0][0]
recursiveSolver(board, 0, 0);
}
private boolean recursiveSolver(char[][] board, int i, int j) {
if (i == 9) // All cells has been given a number, and there is no conflict
return true;
if (j == 9) // Go beyond the last column, go to the first cell in the next row
return recursiveSolver(board, i+1, 0);
if (board[i][j] != ‘.’) { // A fixed number in that cell; go to the next cell
return recursiveSolver(board, i, j+1);
} else { // An empty cell
// Try each possible character
for (int k = 0; k < 9; k++) {
char c = (char)(‘1’+k);
int val = c – ‘1’;
// Test whether putting c in board[i][j] is valid (pass the three checkers)
if (!rowChecker[i][val] && !columnChecker[j][val] && !gridChecker[i/3*3+j/3][val]) {
// Put c in board[i][j] and update state
board[i][j] = c;
rowChecker[i][val] = columnChecker[j][val] = gridChecker[i/3*3+j/3][val] = true;
// If there is a solution given the current state, we are done;
if (recursiveSolver(board, i, j+1))
return true;
// Otherwise, we remove c from board[i][j] and update state, and try next possible value
board[i][j] = ‘.’;
rowChecker[i][val] = columnChecker[j][val] = gridChecker[i/3*3+j/3][val] = false;
}
}
// Cannot get returned from the above loop; no solution exists
return false;
}
}
}

4. Wrapup
The above backtracking solution is in essence a trialanderror algorithm. But since it can prune the brunches that have been found unfeasible in the midway, it is still much better than listing and verifying all possible candidates.