數獨是一種源自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
沒有留言:
張貼留言