DAY 23
1
Software Development

## Day23- project3 - 解經典9x9數獨問題

(還沒看過題目的朋友歡迎點昨日題目傳送門)

``````def trans(state):
return ['.'*state[i]+'Q'+'.'*(len(state)-state[i]-1) for i in range(len(state))]
``````

(參考資料: 數獨- 維基百科)

# 資料型態的選擇- 一維或二維陣列

`"."`表示還沒填上數字的空白格字，

``````sudoku= \
["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"]
``````

# 思考重點: 遞迴關係黑魔法

``````def solveSudoku(board):
ans = [] #記錄所有可能的解答
idx = 題目的第一個空格index
exclude = 所有與board[idx]同一行、列、九宮格形成的集合
for m in set('123456789')-excluded_nums: #嘗試填入不違規的數字
ans += solveSudoku(board[:idx]+[m]+board[idx+1:])
return ans
``````

# 細節思考: 判斷相同的行、列、九宮格

`````` 0  1  2  3  4  5  6  7  8
9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53
54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80
``````

``````def same_row(i,j): return (i//9 == j//9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i//27 == j//27 and i%9//3 == j%9//3)
``````

# 細節思考: 設定遞迴終止條件

`idx`表示題目中第一個空格位置，

`idx``-1`我們就知道說函數該返回了。

``````def solveSudoku(board):
ans = []
idx = board.index('.') if '.' in board else -1
if idx == -1: #解完了
return [board]
exclude = {board[j] for j in range(81) if same_row(idx,j) or same_col(idx,j) or same_block(idx,j)}
for m in set('123456789')-exclude:
ans += solveSudoku(board[:idx]+[m]+board[idx+1:])
return ans
``````

# 大功告成，附上完整程式碼

``````def same_row(i,j): return (i//9 == j//9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i//27 == j//27 and i%9//3 == j%9//3)

def solveSudoku(board):
ans = []
idx = board.index('.') if '.' in board else -1
if idx == -1: #解完了
return [board]
exclude = {board[j] for j in range(81) if same_row(idx,j) or same_col(idx,j) or same_block(idx,j)}
for m in set('123456789')-exclude:
ans += solveSudoku(board[:idx]+[m]+board[idx+1:])
return ans
``````

# 測試解數獨

``````sudoku= \
["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"]

import time
tStart = time.time()#計時開始
print(solveSudoku(S))
tEnd = time.time()#計時結束
print("Total time= %f seconds" % (tEnd - tStart))
``````

`[['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']]`
`Total time= 0.156252 seconds`

# 課後練習- 視覺化印出9x9數獨的解

`[['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']]`

(這件事不一定要用函數包裝起來，你能完成這項功能就好)

``````['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']
``````