LeetCode 37. Sudoku Solver

Problem

LeetCode 37. Sudoku Solver

1. 题目简述

给出一个9 * 9的数独游戏表格，找出它的解（保证有解）。例如：

2. 算法思路

相关问题：

1. LeetCode 36. Valid Sudoku

参考资料：

1. labuladong的算法小抄-数独问题

回溯法

老数独题目了，回溯法可解，就是暴力穷举，回溯法的经典题目之一。我一开始的做法是使用了hashset，其实用hashmap也OK，因为hashset的底层实现就是hashmap，本质上是一样的。

这里我们还要注意创建collections数组的方法，要先创建引用，然后再for循环创建每一个collection实例。

class Solution {
    Set<Character>[] rows = new HashSet[9];
    Set<Character>[] cols = new HashSet[9];
    Set<Character>[] boxes = new HashSet[9];

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<Character>();
            cols[i] = new HashSet<Character>();
            boxes[i] = new HashSet<Character>();
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    rows[i].add(board[i][j]);
                    cols[j].add(board[i][j]);
                    boxes[(i / 3) * 3 + j / 3].add(board[i][j]);
                }
            }
        }

        backtracking(board, 0, 0, rows, cols, boxes);
    }

    private boolean backtracking(char[][] board, int i, int j, Set<Character>[] rows, Set<Character>[] cols, Set<Character>[] boxes) {
        // 到达最后一列，开始对下一行进行回溯
        if (j == 9) {
            return backtracking(board, i + 1, 0, rows, cols, boxes);
        }

        // 完成最后一行，结束，说明找到解了
        if (i == 9) {
            return true;
        }

        int box_id = (i / 3) * 3 + j / 3;
        if (board[i][j] != '.') {
            return backtracking(board, i, j + 1, rows, cols, boxes);
        } else {
            for (char c = '1'; c <= '9'; c++) {
                // 检查当前这个值是否valid
                if (!rows[i].contains(c) && !cols[j].contains(c) && !boxes[box_id].contains(c)) {
                    board[i][j] = c;
                    rows[i].add(c);
                    cols[j].add(c);
                    boxes[box_id].add(c);
                    if (!backtracking(board, i, j + 1, rows, cols, boxes)) {
                        // 回溯
                        rows[i].remove(c);
                        cols[j].remove(c);
                        boxes[box_id].remove(c);
                        board[i][j] = '.';
                        continue;
                    } else {
                        return true;
                    }
                }
            }
            return false;
        }

    }
}

第二种写法是参考的上面参考资料，写法更为优雅，且没有用到hashset或者hashmap，写法上更加优雅，但是速度来说没有hashmap或者hashset快。

class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0);
    }

    boolean backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9;
        if (j == n) {
            // 穷举到最后一列的话就换到下一行重新开始。
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
            // 找到一个可行解，触发 base case
            return true;
        }

        if (board[i][j] != '.') {
            // 如果有预设数字，不用我们穷举
            return backtrack(board, i, j + 1);
        }

        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果遇到不合法的数字，就跳过
            if (!isValid(board, i, j, ch))
                continue;

            board[i][j] = ch;
            // 如果找到一个可行解，立即结束
            if (backtrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.';
        }
        // 穷举完 1~9，依然没有找到可行解，此路不通
        return false;
    }

    boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // 判断行是否存在重复
            if (board[r][i] == n)
                return false;
            // 判断列是否存在重复
            if (board[i][c] == n)
                return false;
            // 判断 3 x 3 方框是否存在重复
            if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
                return false;
        }
        return true;
    }
}