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 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

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.

Analysis

Brute-Force

Each cell could be filled number from 1 to 9 and then check validity. There could be $9^81$ operations to do, where $81$ is the number of cells to fill.

Backtracking

From LeetCode solution section:

The basic idea is to do some pre-processing. We calculate many sets in advance to make operations in backtracking faster. In backtracking, we examine each empty positionâ€™s all possibilities, which could be calculated by set operations.

// You may assume that the given Sudoku puzzle will have a single unique solution. Set<Integer>[] rowSetArr; Set<Integer>[] colSetArr; Set<Integer>[] boxSetArr;

publicvoidsolveSudoku(char[][] board) { initSets(board); // init set List<int[]> steps = getSteps(board); // get steps (get all position (i, j) where it is empty) backtrack(0, steps, board); }

privatebooleanbacktrack(int d, List<int[]> steps, char[][] board) { // Base case if (d == steps.size()) { returntrue; // when a result is found, return immediately } // Step (current empty position) int[] currStep = steps.get(d); inti= currStep[0], j = currStep[1]; // row and column intboxNum= i / 3 * 3 + j / 3; // Set Set<Integer> option = getOptionSet(i, j, boxNum); if (option.size() == 0) returnfalse; // no more option to choose (should backtrack now) // For each option (val) for (int val : option) { // pick board[i][j] = (char) ('0' + val); // convert from int to char. Note: (char) is a must rowSetArr[i].add(val); colSetArr[j].add(val); boxSetArr[boxNum].add(val); if (backtrack(d + 1, steps, board)) returntrue; // restore board[i][j] = '.'; rowSetArr[i].remove(val); colSetArr[j].remove(val); boxSetArr[boxNum].remove(val); } returnfalse; }

private Set<Integer> getOptionSet(int i, int j, int boxNum) { // whole set Set<Integer> wholeSet = newHashSet<>(); for (intval=1; val <= 9; ++val) wholeSet.add(val); wholeSet.removeAll(rowSetArr[i]); // equivalent to doing addAll (union) + removeAll (difference) wholeSet.removeAll(colSetArr[j]); wholeSet.removeAll(boxSetArr[boxNum]); return wholeSet; }