Leetcode P0037"Sudoku Solver" 题解

博文中会简要介绍Leetcode P0037题目分析及解题思路。

“Sudoku Solver”是“看图看题说话”的风格，主要运用深度搜索。这里可以不用HashTable来记录数字出现个数，这样可以减少时间开销。

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

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 ‘.’.

按题目要求的规则写出判断公式，并且通过取出所有空格子连成链表来便利深度搜索。这里我是采取了相对麻烦的方法，即每个格子都重新判断，其实可以维护三个规则的布尔矩阵用于判断，在深度搜索的时候向下传递并且更新。这里就不再赘述。

以下是Java的题解代码实现。

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null)
            return;
        
        List<int[]> pos = new ArrayList<>();
        for (int r=0; r<9; ++r) {
           for (int c=0; c<9; ++c) {
                if (board[r][c] == '.')
                    pos.add(new int[] {r, c});
           }
        }
        
        this.board = board;
        this.dfs(0, pos);
    }
    
    private char[][] board;
    // Directions mapping
    // private int[][] directions;
    // {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}
    
    private boolean dfs(int itr, List<int[]> pos) {
        if (itr >= pos.size()) {
            return true;
        }
        
        for (int digit=1; digit<=9; ++digit) {
            int row = pos.get(itr)[0], col = pos.get(itr)[1];
            if (this.validate(pos.get(itr), digit)) {
                this.board[row][col] = (char)('0'+digit);
                
                // Finished
                if (this.dfs(itr+1, pos))
                    return true;
                
                this.board[row][col] = '.';
            }
        }
        
        return false;
    }
    
    private boolean validate(int[] pos, int digit) {
        int row = pos[0], col = pos[1];
        // Validate subbox
        int[] digitCounterForSubbox = new int[10];
        int centerRow = row/3*3+1, centerCol = col/3*3+1;
        for (int[] di: this.directions) {
            int nextRow = centerRow+di[0];
            int nextCol = centerCol+di[1];
            
            if (this.board[nextRow][nextCol] == '.')
                continue;
            
            ++digitCounterForSubbox[this.board[nextRow][nextCol]-'0'];
        }
        if (digitCounterForSubbox[digit] >= 1)
            return false;
        
        // Validate row
        int[] digitCounterForRow = new int[10];
        for (int c=0; c<9; ++c) {
            if (this.board[row][c] == '.')
                continue;
            
            ++digitCounterForRow[this.board[row][c]-'0'];
        }
        if (digitCounterForRow[digit] >= 1)
            return false;
        
        // Validate column
        int[] digitCounterForCol = new int[10];
        for (int r=0; r<9; ++r) {
            if (this.board[r][col] == '.')
                continue;
            
            ++digitCounterForCol[this.board[r][col]-'0'];
        }
        if (digitCounterForCol[digit] >= 1)
            return false;
        
        return true;
    }
    
}

聖地亞歌

Leetcode P0037"Sudoku Solver" 题解

Search

Table of Contents