a016: 數獨(SUDOKU)

a016: 數獨(SUDOKU)
數獨是一種源自18世紀末的瑞士數學家歐拉(Leonhard Euler)所創造的拉丁方塊游戲。

在9格寬×9格高的大九宮格中有9個3格寬×3格高的小九宮格，已經有一些數字在裡面了(但並非一定採用數字，例如採用字母a,b,c...)，根據這些數字，運用你的邏輯和推理,在其他的空格上填入1到9的數字，但是要注意了，每個數字在每個小九宮格內不能重複，每個數字在每行、每列也不能出現一樣的數字。 這種遊戲只需要邏輯思維能力，與數字運算無關。雖然玩法簡單，但數字排列方式卻千變萬化，所以不少教育者認為數獨是鍛鍊腦筋的好方法。 (wikipedia)

現在我們可以用程式來判斷一個九宮格數字是不是一個數獨的正解。

輸入說明
輸入的每一組測試資料均為 9 × 9 的矩陣，且全部為 1~9 的數字，每兩組九宮格之間以一空行作為分隔

輸出說明
yes or no


# check_sudoku should return None
ill_formed = [[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],  # <---
              [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]]

# check_sudoku should return True
valid = [[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]]

# check_sudoku should return False
invalid = [[5,3,4,6,7,8,9,1,2],
           [6,7,2,1,9,5,3,4,8],
           [1,9,8,3,8,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]]

# check_sudoku should return True
easy = [[2,9,0,0,0,0,0,7,0],
        [3,0,6,0,0,8,4,0,0],
        [8,0,0,0,4,0,0,0,2],
        [0,2,0,0,3,1,0,0,7],
        [0,0,0,0,8,0,0,0,0],
        [1,0,0,9,5,0,0,6,0],
        [7,0,0,0,9,0,0,0,1],
        [0,0,1,2,0,0,3,0,6],
        [0,3,0,0,0,0,0,5,9]]

# check_sudoku should return True
hard = [[1,0,0,0,0,7,0,9,0],
        [0,3,0,0,2,0,0,0,8],
        [0,0,9,6,0,0,5,0,0],
        [0,0,5,3,0,0,9,0,0],
        [0,1,0,0,8,0,0,0,2],
        [6,0,0,0,0,4,0,0,0],
        [3,0,0,0,0,0,0,1,0],
        [0,4,0,0,0,0,0,0,7],
        [0,0,7,0,0,0,3,0,0]]

def nine_by_nine(grid):
    if not grid:
        return False
    if len(grid) != 9:
        return False
    for row in grid:
        if len(row) != 9:
            return False
    return True   

def all_digits(grid):
    for row in grid:
        for cell in row:
            try:
                int_value = int(cell)
                if int_value < 0 or int_value > 9 or int_value != cell:
                    return False
            except:
                return False
    return True 


# checks no duplicates from 1 to 9 (duplicate 0's are ok)
def check_no_dups(nineGrouping): 
    uniqueDigits = set()
    for num in nineGrouping:
      if num != 0:
        if num  in uniqueDigits :
            return False
        uniqueDigits.add(num)
    return True
   

def check_row(grid, row):
    nineGrouping = []
    for cell in grid[row]:
        nineGrouping.append(cell)
    return check_no_dups(nineGrouping)

def check_column(grid, column):
    nineGrouping = []
    for row in grid:
        nineGrouping.append(row[column])
    return check_no_dups(nineGrouping)

def check_subgrid(grid, row, column):
    nineGrouping = []
    for i in range(row, row + 3):
        for j in range(column, column + 3):
            nineGrouping.append(grid[i][j])
    return check_no_dups(nineGrouping)

def check_sudoku(grid):
    if not nine_by_nine(grid) or not all_digits(grid):
      return None
    for i in range(0, 9):
      if not check_row(grid, i):
          return False
      if not check_column(grid, i):
      return False
    for i in range(0, 7, 3):
        for j in range(0, 7, 3):
            if not check_subgrid(grid, i, j):
                return False
    return True
    pass


print (check_sudoku(ill_formed)) # --> None
print (check_sudoku(valid))      # --> True
print (check_sudoku(invalid))    # --> False
print (check_sudoku(easy))       # --> True
print (check_sudoku(hard))       # --> True