leetcode第36題-有效的數獨

上圖是一個部分填充的有效的數獨。

數獨部分空格內已填入了數字，空白格用 '.' 表示。

示例 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 存在, 因此這個數獨是無效的。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/valid-sudoku

解答

def is_valid_sudoku(board):
    """
    自己寫的
    :type board: List[List[str]]
    :rtype: bool
    """
    dict_column = {}  # 列的集合
    for a in range(9):
        dict_column[a] = []
    dict_block = {}  # 3X3方塊的集合
    for b in range(9):
        dict_block[b] = []

    for i in range(len(board)):
        for j in range(len(board)):
            # 判斷行
            if (board[i][j] != '.') and (board[i].count(board[i][j]) > 1):
                return False
            # 裝填dict_column
            dict_column[j].append(board[i][j])
        # 裝填dict_block
        for k in range(3):
            dict_block[i/3+k+i/3*2].extend(board[i][3*k:3*k+3])

    # 判斷列
    for column in dict_column.values():
        for x in range(8):  # 最後一個必定不會重複，所以不用判斷
            if (column[x] != '.') and (column.count(column[x]) > 1):
                return False
    # 判斷3X3方塊
    for block in dict_block.values():
        for y in range(8):
            if (block[y] != '.') and (block.count(block[y]) > 1):
                return False
    return True

官方解法

首先，讓我們來討論下面兩個問題：

可以使用 box_index = (row / 3) * 3 + columns / 3，其中 / 是整數除法。

可以利用 value -> count 哈希映射來跟蹤所有已經遇到的值。

現在，我們完成了這個算法的所有準備工作：

def is_valid_sudoku1(board):
    # init data
    rows = [{} for i in range(9)]
    columns = [{} for i in range(9)]
    boxes = [{} for i in range(9)]

    # validate a board
    for i in range(9):
        for j in range(9):
            num = board[i][j]
            if num != '.':
                num = int(num)
                box_index = (i // 3) * 3 + j // 3

                # keep the current cell value
                rows[i][num] = rows[i].get(num, 0) + 1
                print rows[i][num]
                columns[j][num] = columns[j].get(num, 0) + 1
                boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

                # check if this value has been already seen before
                if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                    return False
    return True


if __name__ == "__main__":
    a=[
  ["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"]
]
    b=[
  ["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"]
]
    print is_valid_sudoku1(a)
    print is_valid_sudoku1(b)