leetcode 036. 有效的数独

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

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

image

上图是一个部分填充的有效的数独。

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

示例 1:

输入:
[
["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:

输入:
[
["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. 判断行和列是否有重复值，按一行和一列同时循环，分别判断2个值当前值是否在行字典内，或者是否在列字典内，如图，逐行扫描完整个表。

2. 把表划成9个宫，每个宫内扫描是否有重复值。

   
   Image.png

class Solution:
    def isValidSudoku(self, board):
        # 先判断行和列是否有重复数字，向后进行判断，判断过的不再判断
        for x in range(9):
            row_dic = {}
            col_dic = {}
            for y in range(9):
                if board[x][y] != '.':
                    if board[x][y] in row_dic or board[x][y] < '1' or board[x][y] > '9':
                        return False
                    row_dic[board[x][y]] = 1
                if board[y][x] != '.':
                    if board[y][x] in col_dic or board[y][x] < '1' or board[y][x] > '9':
                        return False
                    col_dic[board[y][x]] = 1
        # 分成9个区域进行处理，每个区域单独判断
        coordinate = [(i, j) for i in range(0, 9, 3) for j in range(0, 9, 3)]
        for i, j in coordinate:
            cell_dic = {}
            for x in range(3):
                for y in range(3):
                    x_move = i + x
                    y_move = j + y
                    if board[x_move][y_move] != '.':
                        if board[x_move][y_move] in cell_dic or board[x_move][y_move] < '1' or board[x_move][y_move] > '9':
                            return False
                        cell_dic[board[x_move][y_move]] = 1

        return True


su = Solution()
board = [
  ["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"]
]
res = su.isValidSudoku(board)
print(res)