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); int i = currStep[0], j = currStep[1]; // row and column int boxNum = 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 = new HashSet<>(); for (int val = 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; }

privatevoidinitSets(char[][] board){ // row/col/box sets rowSetArr = new HashSet[9]; colSetArr = new HashSet[9]; boxSetArr = new HashSet[9]; for (int i = 0; i < 9; ++i) { rowSetArr[i] = new HashSet<>(); colSetArr[i] = new HashSet<>(); boxSetArr[i] = new HashSet<>(); } for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { char ch = board[i][j]; if (ch == '.') continue; rowSetArr[i].add(ch - '0'); colSetArr[j].add(ch - '0'); boxSetArr[i / 3 * 3 + j / 3].add(ch - '0'); } } }

private List<int[]> getSteps(char[][] board) { List<int[]> steps = new ArrayList<>(); for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { char ch = board[i][j]; if (ch == '.') { steps.add(newint[] { i, j }); // cannot specify length in this case } } } return steps; }