"""
day: 2020-08-11
url: https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2f9gg/
题目名: 有效的数独
题目描述: 判断一个9x9的数独是否有效,根据以下规则,验证已经填入的数字是否有效即可
    1. 数字1-9在每一行只能出现一次
    2. 数字1-9在每一列只能出现一次
    3. 数字1-9在每一个以粗实线分割的3x3宫内只能出现一次
示例:
    输入:
    [
        ["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
    输入:
    [
      ["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
    解释: 左上角3x3宫内有两个8存在
说明:
    一个有效的数独不一定是可解的
思路:
1. 用字典存储数字出现的次数
    分别定义行字典列表,列字典列表,块字典列表
    遍历数组,把值存储到它对应的行字典,列字典,块字典中,然后判断数字出现的次数

2. 利用set去重
    将每一行,每一列,每一块都的数字除'.'外分别保存到一个列表中,最后使用all方法
    +len(list) == len(set)来判断是否有重复元素
"""


class Solution(object):
    @staticmethod
    def isValidSudoku(board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        rows = [{} for _ in range(9)]
        columns = [{} for _ in range(9)]
        boxes = [{} for _ in range(9)]

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    box_index = (i // 3) * 3 + j // 3
                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True

        # row = [[x for x in y if x != '.'] for y in board]
        # col = [[x for x in y if x != '.'] for y in zip(*board)]
        # box = [[board[i+m][j+n] for m in range(3) for n in range(3) if board[i+m][j+n] != '.'] for i in (0, 3 ,6) for j in (0, 3, 6)]
        # return all(len(item) == len(set(item)) for item in (*row, *col, *box))


if __name__ == "__main__":
    test = [
        ["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"]
    ]
    print(Solution.isValidSudoku(test))
