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;
                }

                presentRow.get(i).add(board[i][j]);
            }
        }

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

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

                presentCol.get(i).add(board[j][i]);
            }
        }

        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;
                        }

                        presentSubBox.get(key).add(board[x][y]);
                    }
                }
            }
        }

        updateCandidate(board);

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

        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;

        presentRow.get(x).add(val);
        presentCol.get(y).add(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
        // reverse operations as add().

        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(presentRow.get(i));
                present.addAll(presentCol.get(j));
                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;
                    }

                    candidate.get(key).add((char)x);
                }
            }
        }

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

Incorrect Solutions

References