# 37. Sudoku Solver (Hard)

https://leetcode.com/problems/sudoku-solver/

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. 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 `'.'`.

A sudoku puzzle...

...and its solution numbers marked in red.

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`.

## Solutions

``````class Solution {
// It takes too much time, ignore this problem

// keep the present values in specific row
Map<Integer, Set<Character>> presentRow = new HashMap<>();

// keep the present values in specific column
Map<Integer, Set<Character>> presentCol = new HashMap<>();

// keep the present values in specific sub-box
Map<String, Set<Character>> presentSubBox = new HashMap<>();

// keep the candidates for a specific cell
Map<String, Set<Character>> candidate = new HashMap<>();

PriorityQueue<String> queue = new PriorityQueue<>(Comparator.comparingInt(o -> candidate.get(o).size()));

char[][] ans = null;

public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
presentRow.put(i, new HashSet<>());

for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
continue;
}

}
}

for (int i = 0; i < 9; i++) {
presentCol.put(i, new HashSet<>());

for (int j = 0; j < 9; j++) {
if (board[j][i] == '.') {
continue;
}

}
}

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
String key = i + "#" + j;
presentSubBox.put(key, new HashSet<>());

for (int x = i * 3; x < (i+1) * 3; x++) {
for (int y = j * 3; y < (j+1) * 3; y++) {
if (board[x][y] == '.') {
continue;
}

}
}
}
}

updateCandidate(board);

for (String key : candidate.keySet()) {
}

check(board);

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = ans[i][j];
}
}
}

private boolean check(char[][] board) {
if (queue.isEmpty()) {
ans = new char[9][9];

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
ans[i][j] = board[i][j];
}
}

return true;
}

// no loop here.

String key = queue.poll();

String[] cell = key.split("#");
int x = Integer.valueOf(cell[0]);
int y = Integer.valueOf(cell[1]);

Set<Character> set = candidate.get(key);

// run out of candidates for certain cell, not workable solution
if (set.size() == 0) {
return false;
}

for (Character c : set) {

// if already find the solution, return directly
if (ans != null) {
return true;
}

// If it does not violate the constraints
if (add(board, x, y, c)) {
// the candidate char is a valid one

// recheck processed board
check(board);
}

// undo value setting
remove(board, x, y);
}

// If solution found, the execution will return in the loop. To reach here,
// no correct solution found.

// no valid solution found.
return false;
}

private boolean add(char[][] board, int x, int y, char val) {
// board[x][y] is the candidate in candidate set

// check presentRow if value val is suitable for board[x][y],
// in other words, not exists in presentRow
if (presentRow.get(x).contains(val)) {
return false;
}

// check presentCol if value val is suitable for board[x][y]
if (presentCol.get(y).contains(val)) {
return false;
}

// check presentSubBox if value val is suitable for board[x][y]
if (presentSubBox.get((x / 3) + "#" + (y / 3)).contains(val)) {
return false;
}

// if all suitable, set board[x][y] to val and update presentRow,
// presentCol and presetSubBox.

board[x][y] = val;

presentSubBox.get((x / 3) + "#" + (y / 3)).add(val);

updateCandidate(board);

return true;
}

private void remove(char[][] board, int x, int y) {
// Similar with add(), but no need to check validaty, just do

char val = board[x][y];

presentRow.get(x).remove(val);
presentCol.get(y).remove(val);
presentSubBox.get((x / 3) + "#" + (y / 3)).remove(val);

board[x][y] = '.';

updateCandidate(board);
}

private void updateCandidate(char[][] board) {
// update constraints with newly add board[x][y]=c

candidate.clear();

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
continue;
}

Set<Character> present = new HashSet<>();
present.addAll(presentSubBox.get((i / 3) + "#" + (j / 3)));

String key = i + "#" + j;
candidate.put(key, new HashSet<>());

for (int x = '1'; x <= '9'; x++) {
if (present.contains((char)x)) {
continue;
}

}
}
}

queue.clear();
for (String key : candidate.keySet()) {
}
}
}
``````