37. Sudoku Solver

三刷 07/2022

Version #2 DFS backtracking - only place valid character

跟之前写的不一样

之前是随便放然后检查是不是valid

这个写法是先把整个board走一遍求出已经放了的numbers，然后每次每个空格只放可以成功的数

有点慢，但是感觉问题不大

Time O((9!)^9) for each row there are 9! possibilities, and total 9 rows

Space O(3 * 9^2)

Runtime: 43 ms, faster than 8.54% of Java online submissions for Sudoku Solver.

Memory Usage: 46.4 MB, less than 7.44% of Java online submissions for Sudoku Solver.

class Solution {

    public void solveSudoku(char[][] board) {

        List<Set<Character>> rowSets = new ArrayList<>();

        List<Set<Character>> colSets = new ArrayList<>();

        List<Set<Character>> subSets = new ArrayList<>();

        // the index of sub-box is y/3 * 3 + x/3

        for (int i = 0; i < 9; i++) {

            rowSets.add(new HashSet<>());

            colSets.add(new HashSet<>());

            subSets.add(new HashSet<>());

        }

        for (int y = 0; y < board.length; y++) {

            for (int x = 0; x < board[0].length; x++) {

                if (board[y][x] == '.') {

                    continue;

                }

                rowSets.get(y).add(board[y][x]);

                colSets.get(x).add(board[y][x]);

                subSets.get(subIndex(y, x)).add(board[y][x]);

            }

        }

        fillBoard(board, rowSets, colSets, subSets, 0, 0);

    }

    

    private boolean fillBoard(char[][] board, List<Set<Character>> rowSets, List<Set<Character>> colSets, List<Set<Character>> subSets, int y, int x) {

        if (y == board.length) {

            return true;

        }

        int nextX = x + 1;

        int nextY = y;

        if (nextX == board[0].length) {

            nextY = y + 1;

            nextX = 0;

        }

        if (board[y][x] != '.') {

            return fillBoard(board, rowSets, colSets, subSets, nextY, nextX);

        }

        for (char c = '1'; c <= '9'; c++) {

            int si = subIndex(y, x);

            if (rowSets.get(y).contains(c) || colSets.get(x).contains(c) || subSets.get(si).contains(c)) {

                continue;

            }

            rowSets.get(y).add(c);

            colSets.get(x).add(c);

            subSets.get(si).add(c);

            board[y][x] = c;

            if (fillBoard(board, rowSets, colSets, subSets, nextY, nextX)) {

                return true;

            }

            rowSets.get(y).remove(c);

            colSets.get(x).remove(c);

            subSets.get(si).remove(c);

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

        }

        return false;

    }

    

    private int subIndex(int y, int x) {

        return y / 3 * 3 + x / 3;

    }

}

Version #1 DFS backtracking

二刷

25.00 %
class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
   
    private boolean solve(char[][] board) {
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[0].length; x++) {
                if (board[y][x] == '.') {
                    for (char i = '1'; i <= '9'; i++) {
                        board[y][x] = i;
                        if (isValid(board, y, x) && solve(board)) {
                            return true;
                        }
                    }
                    board[y][x] = '.';
                    return false;
                }
            }
        }
        // all filled
        return true;
    }
   
    private boolean isValid(char[][] board, int y, int x) {
        for (int i = 0; i < 9; i++) {
            if (i != x && board[y][i] == board[y][x]) {
                return false;
            }
            if (i != y && board[i][x] == board[y][x]) {
                return false;
            }
            int nextY = y / 3 * 3 + i / 3;
            int nextX = x / 3 * 3 + i % 3;
            if ((nextY != y || nextX != x) && board[nextY][nextX] == board[y][x]) {
                return false;
            }
        }
        return true;
    }
}

一刷
确实挺难的，难在一开始没有想到每次都从头到尾扫一遍
还有就是确定每个小九宫格的坐标，通过x / 3 * 3, y / 3 * 3来取得小九宫格的start index

64.79 %
class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
 
    private boolean solve(char[][] board) {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                if (board[y][x] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        board[y][x] = c;
                        if (isValid(board, y, x) && solve(board)) {
                            return true;
                        }
                    }
                    board[y][x] = '.';
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int y, int x) {
        for (int i = 0; i < 9; i++) {
            if (i != y && board[i][x] == board[y][x]
                || i != x && board[y][i] == board[y][x]) return false;
        }
        int startX = x / 3 * 3;
        int startY = y / 3 * 3;
        for (int dy = 0; dy < 3; dy++) {
            for (int dx = 0; dx < 3; dx++) {
                if (startX + dx == x && startY + dy == y) continue;
                if (board[startY + dy][startX + dx] == board[y][x]) return false;
            }
        }
        return true;
    }
}