Leetcode(37) Sudoku Solver

发表于 | 分类于

Description

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

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. 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 '.'.

img
A sudoku puzzle…

img
…and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

解法

填表格问题，深度优先搜索。只需要对每一个插入的新元素进行合法性判断即可，因为之前插入的数一定是合法的。注意在搜索失败时需将赋值的点还原为未赋值的状态，相当于回溯。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public void solveSudoku(char[][] board) {
        if (board.length != 9 || board[0].length != 9) {
            return;
        }
        dfs(board, 0, 0);
    }

    boolean dfs(char[][] board, int row, int col) {
        if (row == 9) {
            return true;
        }
        if (board[row][col] == '.') {
            for (int i = 1; i <= 9; i++) {
                board[row][col] = (char) ('0' + i);
                if (isValid(board, row, col)) {
                    if (col == 8) {
                        if (dfs(board, row + 1, 0)) {
                            return true;
                        }
                    } else {
                        if (dfs(board, row, col + 1)) {
                            return true;
                        }
                    }
                }
                board[row][col] = '.';
            }
            return false;
        } else {
            if (col == 8) {
                return dfs(board, row + 1, 0);
            } else {
                return dfs(board, row, col + 1);
            }
        }
    }

    //判读插入数组是否合法
    boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == board[row][col] && i != row) {
                return false;
            }
        }
        for (int j = 0; j < board[0].length; j++) {
            if (board[row][j] == board[row][col] && j != col) {
                return false;
            }
        }
        for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
            for (int j = col / 3 * 3; j < col / 3 * 3 + 3; j++) {
                if (board[i][j] == board[row][col] && (i != row || j != col)) {
                    return false;
                }
            }
        }
        return true;
    }
}