题目描述

[EN | CN]

判断一个 9x9 的数独是否有效。只需要 根据以下规则,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

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

示例 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
输入:
[
  ["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"]
]
输出: true

示例 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
输入:
[
  ["8", "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"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

  • 一个有效的数独(部分已被填充)不一定是可解的。
  • 只需要根据以上规则,验证已经填入的数字是否有效即可。
  • 给定数独序列只包含数字 1-9 和字符 '.' 。
  • 给定数独永远是 9x9 形式的。

解法 1:直接法

这道题比较简单,就是验证数独表格中当前数据是否有效(用 set 来解决),分别判断行、列、小方块。

复杂度分析略。

实现与结果如下:

 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
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def is_valid_list(list_):
            set_ = set()
            for c in list_:
                if c == '.':
                    continue
                elif c in set_:
                    return False
                else:
                    set_.add(c)
            return True

        for row in board:
            if not is_valid_list(row):
                return False

        for col in list(zip(*board)):
            if not is_valid_list(col):
                return False

        for i in range(3):
            for j in range(3):
                flatten_square = [c for row in board[i * 3: i * 3 + 3]
                                  for c in row[j * 3: j * 3 + 3]]
                if not is_valid_list(flatten_square):
                    return False

        return True
  • 执行用时:56 ms,在所有 Python3 提交中击败了 63.28% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 9.09% 的用户。