37. 解数独

发表评论
421 views

 ›
37. 解数独

官方链接

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

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

思路

  1. DFS j+1 ->i+i,j

  2. 优化

    将正方形按照可选数进行排序，从可选数最小的开始解决，重新排序可选树，循环解决

  3. Dancinglink

  4. 位运算

解法一

class Solution {
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c) return false; // check row
            if (board[row][i] != '.' && board[row][i] == c) return false; // check column
            if (board[(row/3)*3+i/3][(col/3)*3+i%3] != '.' && board[(row/3)*3+i/3][(col/3)*3+i%3] == c) return false; // check 3*3 block
        }
        return true;
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if(isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public void solveSudoku(char[][] board) {
        solve(board);
    }
}

解法二

class Solution {
    private boolean dfs(char[][] board, int d) {
        if (d == 81) return true;
        int i = d / 9, j = d % 9;
        if (board[i][j] != '.') return dfs(board, d + 1);

        boolean[] flag = new boolean[10];
        validate(board, i, j, flag);

        for (int k = 1; k <= 9; k++) {
            if (flag[k]) {
                board[i][j] = (char) ('0' + k);
                if (dfs(board, d + 1)) return true;
            }
        }
        board[i][j] = '.';
        return false;
    }

    private void validate(char[][] board, int i, int j, boolean[] flag) {
        Arrays.fill(flag, true);
        for (int k = 0; k < 9; k++) {
            if (board[i][k] != '.') flag[board[i][k] - '0'] = false;
            if (board[k][j] != '.') flag[board[k][j] - '0'] = false;

            int r = i / 3 * 3 + k / 3;
            int c = j / 3 * 3 + k % 3;
            if (board[r][c] != '.') flag[board[r][c] - '0'] = false;
        }
    }

    public void solveSudoku(char[][] board) {
        dfs(board, 0);
    }
}

解法三

回溯

class Solution {

    int n = 3;
    // row size
    int N = n * n;

    char[][] board;

    int [][] rows = new int[N][N + 1];
    int [][] columns = new int[N][N + 1];
    int [][] boxes = new int[N][N + 1];

    boolean sudokuSolved = false;

    public boolean couldPlace(int d, int row, int col) {
        int idx = (row/n) * n + col / n;
        return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
    }

    public void placeNumber(int d, int row, int col) {

        int idx = (row/n) * n + col / n;
        rows[row][d]++;
        columns[col][d]++;
        boxes[idx][d]++;

        board[row][col] = (char)(d + '0');
    }

    public void backTrack(int row, int col) {
        if (board[row][col] == '.') {
            for(int d = 1; d < 10; d++) {
                if(couldPlace(d, row, col)) {
                    placeNumber(d, row, col);
                    placeNextNumbers(row, col);
                    if (!sudokuSolved) removeNumber(d, row, col);
                }
            }
        } else placeNextNumbers(row, col);
    }

    public void removeNumber(int d, int row, int col) {
        int idx = (row/n) * n + col / n;
        rows[row][d]--;
        columns[col][d]--;
        boxes[idx][d]--;

        board[row][col] = '.';
    }

    public void placeNextNumbers(int row, int col) {
        if ((row == N - 1) && (col == N - 1)) {
            sudokuSolved = true;
        } else {
            if (col == N - 1) backTrack(row + 1, 0);
            else backTrack(row, col + 1);
        }
    }

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

        this.board = board;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] != '.') {
                    int d = Character.getNumericValue(board[i][j]);
                    placeNumber(d, i, j);
                }
            }
        }
        backTrack(0, 0);
    }
}

解法四

https://leetcode-cn.com/problems/sudoku-solver/solution/pythonsethui-su-chao-guo-95-by-mai-mai-mai-mai-zi/

def solveSudoku(self, board: List[List[str]]) -> None:
        row = [set(range(1, 10)) for _ in range(9)]  # 行剩余可用数字
        col = [set(range(1, 10)) for _ in range(9)]  # 列剩余可用数字
        block = [set(range(1, 10)) for _ in range(9)]  # 块剩余可用数字

        empty = []  # 收集需填数位置
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':  # 更新可用数字
                    val = int(board[i][j])
                    row[i].remove(val)
                    col[j].remove(val)
                    block[(i // 3)*3 + j // 3].remove(val)
                else:
                    empty.append((i, j))

        def backtrack(iter=0):
            if iter == len(empty):  # 处理完empty代表找到了答案
                return True
            i, j = empty[iter]
            b = (i // 3)*3 + j // 3
            for val in row[i] & col[j] & block[b]:
                row[i].remove(val)
                col[j].remove(val)
                block[b].remove(val)
                board[i][j] = str(val)
                if backtrack(iter+1):
                    return True
                row[i].add(val)  # 回溯
                col[j].add(val)
                block[b].add(val)
            return False
        backtrack()