友链
姚屹晨

leetcode - [37] Sudoku Solver

2020/06/22

问题描述

完成一个9*9的数独拼图。

规则如下：

每行、列只能放置1-99个数字，且每个数组只能出现一次。

将棋盘分成9个3*3的小棋盘，每个小棋盘也只能放置1-9个数字，且每个数组只能出现一次。

举个例子：

Update at 2020_0730

多谢Y总，来看下另一种解法：

class Solution {
    
    int N = 9;
    boolean[][] row = new boolean[N][N];
    boolean[][] col = new boolean[N][N];
    boolean[][][] cell = new boolean[N / 3][N / 3][N];
    
    // board[x, y]代表当前单元
    private boolean dfs(char[][] board, int x, int y){
        
        // 1. 边缘条件，纵坐标走到最右侧，换成下一行的开头。
        if (y == N){
            y = 0;
            x++;
        }
        
        // 2. 终止条件，说明这个数独已构建完成。
        if (x == N) return true;
        
        // 3. 当前结点已有值，直接递归遍历下一个单元。
        if (board[x][y] != '.'){
            return dfs(board, x, y + 1);
        }
        
        // 4. 当前结点无值
        for (int i = 0; i < N; i++){
            // 判断当前单元是否能放值i + 1，注意i是索引。
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){
                // 当前值可以放在当前单元
                board[x][y] = (char) (i + '1');
                // 标记一下这个单元已经放了值
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                // dfs
                if (dfs(board, x, y + 1)) return true;
                // 恢复现场
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
                board[x][y] = '.';
            }
        }
        // 5. 说明该数独无解
        return false;
    }
    
    public void solveSudoku(char[][] board) {
        
        // 初始化
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (board[i][j] != '.'){
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
            }
        }
        
        dfs(board, 0, 0);
    }
}

解法1

Thanks @cdai

此题也应该使用回溯思想。

思路如下：

首先，依次遍历9*9的棋盘，一旦遇到数字，直接跳过。

然后，依次尝试1-99个数字，判断放在的当前单元上是否有效。

来看下判断方法：

private boolean isValid(char[][] board, int i, int j, char num){
    
    int cellLo = i / 3 * 3;
    int cellHi = j / 3 * 3;
    
    for (int m = 0; m < 9; m++){
        // Check row
        if (board[i][m] == num) return false;
        // Check column
        if (board[m][j] == num) return false;
        // Check cell
        if (board[cellLo + m / 3][cellHi + m % 3] == num) return false;
    }
    return true;
}

接着，就是常规的回溯操作：

board[i][j] = c;
if (bt(board, row, col + 1)) return true;
board[i][j] = '.';

来看下实现：

class Solution {
    public void solveSudoku(char[][] board) {
        
        if (board == null || board.length == 0) return;
        bt(board, 0, 0);
    }
    
    private boolean bt(char[][] board, int row, int col){
        
        for (int i = row; i < 9; i++, col = 0){
            for (int j = col; j < 9; j++){
                if (board[i][j] != '.') continue;
                for (char c = '1'; c <= '9'; c++){
                    if (isValid(board, i, j, c)){
                        board[i][j] = c;
                        if (bt(board, row, col + 1)) return true;
                        board[i][j] = '.';    
                    }
                }
                return false;
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int i, int j, char num){
        
        int cellLo = i / 3 * 3;
        int cellHi = j / 3 * 3;
        
        for (int m = 0; m < 9; m++){
            // Check row
            if (board[i][m] == num) return false;
            // Check column
            if (board[m][j] == num) return false;
            // Check cell
            if (board[cellLo + m / 3][cellHi + m % 3] == num) return false;
        }
        return true;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory