跳转至

37. 解数独

题目描述

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

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

 

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

 

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

解法

方法一：回溯

我们用数组 row、col、box 分别记录每一行、每一列、每个 3x3 宫格中数字是否出现过。如果数字 i 在第 r 行、第 c 列、第 b 个 3x3 宫格中出现过，那么 row[r][i]、col[c][i]、box[b][i] 都为 true。

我们遍历 board 的每一个空格，枚举它可以填入的数字 v，如果 v 在当前行、当前列、当前 3x3 宫格中没有出现过，那么我们就可以尝试填入数字 v，并继续搜索下一个空格。如果搜索到最后，所有空格填充完毕，那么就说明找到了一个可行解。

时间复杂度 $O(9^{81})$，空间复杂度 $O(9^2)$。

 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
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(k):
            nonlocal ok
            if k == len(t):
                ok = True
                return
            i, j = t[k]
            for v in range(9):
                if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
                    board[i][j] = str(v + 1)
                    dfs(k + 1)
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
                if ok:
                    return

        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
        t = []
        ok = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    t.append((i, j))
                else:
                    v = int(board[i][j]) - 1
                    row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
        dfs(0)

 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
class Solution {
    private boolean ok;
    private char[][] board;
    private List<Integer> t = new ArrayList<>();
    private boolean[][] row = new boolean[9][9];
    private boolean[][] col = new boolean[9][9];
    private boolean[][][] block = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    t.add(i * 9 + j);
                } else {
                    int v = board[i][j] - '1';
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                }
            }
        }
        dfs(0);
    }

    private void dfs(int k) {
        if (k == t.size()) {
            ok = true;
            return;
        }
        int i = t.get(k) / 9, j = t.get(k) % 9;
        for (int v = 0; v < 9; ++v) {
            if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
                row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                board[i][j] = (char) (v + '1');
                dfs(k + 1);
                row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
            }
            if (ok) {
                return;
            }
        }
    }
}

 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
using pii = pair<int, int>;

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        bool row[9][9] = {false};
        bool col[9][9] = {false};
        bool block[3][3][9] = {false};
        bool ok = false;
        vector<pii> t;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    t.push_back({i, j});
                } else {
                    int v = board[i][j] - '1';
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                }
            }
        }
        function<void(int k)> dfs = [&](int k) {
            if (k == t.size()) {
                ok = true;
                return;
            }
            int i = t[k].first, j = t[k].second;
            for (int v = 0; v < 9; ++v) {
                if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                    board[i][j] = v + '1';
                    dfs(k + 1);
                    row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
                }
                if (ok) {
                    return;
                }
            }
        };
        dfs(0);
    }
};

 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
func solveSudoku(board [][]byte) {
    var row, col [9][9]bool
    var block [3][3][9]bool
    var t [][2]int
    ok := false
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                t = append(t, [2]int{i, j})
            } else {
                v := int(board[i][j] - '1')
                row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
            }
        }
    }
    var dfs func(int)
    dfs = func(k int) {
        if k == len(t) {
            ok = true
            return
        }
        i, j := t[k][0], t[k][1]
        for v := 0; v < 9; v++ {
            if !row[i][v] && !col[j][v] && !block[i/3][j/3][v] {
                row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
                board[i][j] = byte(v + '1')
                dfs(k + 1)
                row[i][v], col[j][v], block[i/3][j/3][v] = false, false, false
            }
            if ok {
                return
            }
        }
    }
    dfs(0)
}

  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
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
public class Solution {
    public void SolveSudoku(char[][] board) {
        this.board = new ushort?[9,9];
        for (var i = 0; i < 9; ++i)
        {
            for (var j = 0; j < 9; ++j)
            {
                if (board[i][j] != '.')
                {
                    this.board[i, j] = (ushort) (1 << (board[i][j] - '0' - 1));
                }
            }
        }

        if (SolveSudoku(0, 0))
        {
            for (var i = 0; i < 9; ++i)
            {
                for (var j = 0; j < 9; ++j)
                {
                    if (board[i][j] == '.')
                    {
                        board[i][j] = '0';
                        while (this.board[i, j].Value != 0)
                        {
                            board[i][j] = (char)(board[i][j] + 1);
                            this.board[i, j] >>= 1;
                        }
                    }
                }
            }
        }
    }

    private ushort?[,] board;

    private bool ValidateHorizontalRule(int row)
    {
        ushort temp = 0;
        for (var i = 0; i < 9; ++i)
        {
            if (board[row, i].HasValue)
            {
                if ((temp | board[row, i].Value) == temp)
                {
                    return false;
                }
                temp |= board[row, i].Value;
            }
        }
        return true;
    }

    private bool ValidateVerticalRule(int column)
    {
        ushort temp = 0;
        for (var i = 0; i < 9; ++i)
        {
            if (board[i, column].HasValue)
            {
                if ((temp | board[i, column].Value) == temp)
                {
                    return false;
                }
                temp |= board[i, column].Value;
            }
        }
        return true;
    }

    private bool ValidateBlockRule(int row, int column)
    {
        var startRow = row / 3 * 3;
        var startColumn = column / 3 * 3;
        ushort temp = 0;
        for (var i = startRow; i < startRow + 3; ++i)
        {
            for (var j = startColumn; j < startColumn + 3; ++j)
            {
                if (board[i, j].HasValue)
                {
                    if ((temp | board[i, j].Value) == temp)
                    {
                        return false;
                    }
                    temp |= board[i, j].Value;
                }
            }
        }
        return true;
    }

    private bool SolveSudoku(int i, int j)
    {
        while (true)
        {
            if (j == 9)
            {
                ++i;
                j = 0;
            }
            if (i == 9)
            {
                return true;
            }
            if (board[i, j].HasValue)
            {
                ++j;
            }
            else
            {
                break;
            }
        }

        ushort stop = 1 << 9;
        for (ushort t = 1; t != stop; t <<= 1)
        {
            board[i, j] = t;
            if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j))
            {
                if (SolveSudoku(i, j + 1))
                {
                    return true;
                }
            }
        }
        board[i, j] = null;
        return false;
    }
}

 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    /**
     * @param string[][] $board
     * @return bool
     */

    public function solveSudoku(&$board) {
        if (isSolved($board)) {
            return true;
        }

        $emptyCell = findEmptyCell($board);
        $row = $emptyCell[0];
        $col = $emptyCell[1];

        for ($num = 1; $num <= 9; $num++) {
            if (isValid($board, $row, $col, $num)) {
                $board[$row][$col] = (string) $num;
                if ($this->solveSudoku($board)) {
                    return true;
                }
                $board[$row][$col] = '.';
            }
        }
        return false;
    }
}

function isSolved($board) {
    foreach ($board as $row) {
        if (in_array('.', $row)) {
            return false;
        }
    }
    return true;
}

function findEmptyCell($board) {
    for ($row = 0; $row < 9; $row++) {
        for ($col = 0; $col < 9; $col++) {
            if ($board[$row][$col] === '.') {
                return [$row, $col];
            }
        }
    }

    return null;
}

function isValid($board, $row, $col, $num) {
    for ($i = 0; $i < 9; $i++) {
        if ($board[$row][$i] == $num) {
            return false;
        }
    }

    for ($i = 0; $i < 9; $i++) {
        if ($board[$i][$col] == $num) {
            return false;
        }
    }

    $startRow = floor($row / 3) * 3;
    $endCol = floor($col / 3) * 3;

    for ($i = 0; $i < 3; $i++) {
        for ($j = 0; $j < 3; $j++) {
            if ($board[$startRow + $i][$endCol + $j] == $num) {
                return false;
            }
        }
    }

    return true;
}

评论