###### tags: `程式設計` `Python`
# 第十二週
遞迴思路:
1. 分析需要哪些infomation
以數獨這題來說:
我們需要`board`來記錄當前填了那些數字；

也需要`rowNum`，記錄某列還有哪些數字待填入，填入board則將此數從rowNum中移除；
反之`colNum`亦然，紀錄某行還有哪些數待填，填入board則將此數從colNum中移除
而`blockNum`則是，紀錄某區還有哪些數待填，填入board則將此數從blockNum中移除

另外，我們還需要一個`x`來記錄，填到第幾個格子了

ps我們可以藉由x算出此位置所在哪條row 哪條col 哪個block中:
棋盤內一共有9 row, 9 col, 9 block
位置x屬於
第 `x//9` row
第 `x%9` col
第 `x//27*3+x%9//3` block

2. 選擇資料型態 ex一維、二維
以老師寫的數獨來說:
board是長度81的一維list
rowNum, colNum, blockNum都是9*9的二維list

3. 寫註解定邏輯思路
請見老師的註解

## 數獨

#board: 81個數字, 非0代表已確定 只能填該數字
#rowNum: 某橫列還有哪些是數字是可能的
#colNum: 某直行還有哪些是數字是可能的
#blockNum: 某區塊還有哪些是數字是可能的
def markKnown(board, rowNum, colNum, blockNum):
    for x in range(81): #
        if board[x] != 0:
            rowNum[x//9].remove(board[x])
            colNum[x%9].remove(board[x])
            blockNum[x//27*3 + x%9//3].remove(board[x])
            
#board: 81格內的數字
#x:要負責填第幾個格子
#rowNum: 某橫列還有哪些是數字是可能的
#colNum: 某直行還有哪些是數字是可能的
#blockNum: 某區塊還有哪些是數字是可能的
def fill(board, x, rowNum, colNum, blockNum):
    if x == 81:
        for i in range(9):
            print(*board[i*9:(i+1)*9])
        return
    if board[x] != 0:
        fill(board, x+1, rowNum, colNum, blockNum)
        return
    for i in range(1, 10):#1~9每個檢查一下能不能填
        if i in rowNum[x//9] and i in colNum[x%9] and i in blockNum[x//27*3 + x%9//3] :
            rowNum[x//9].remove(i)
            colNum[x%9].remove(i)
            blockNum[x//27*3+x%9//3].remove(i)
            board[x] = i
            fill(board, x+1, rowNum, colNum, blockNum)
            rowNum[x//9].append(i)
            colNum[x%9].append(i)
            blockNum[x//27*3 + x%9//3].append(i)
            board[x] = 0
            
def findSol(board):
    #有9個row,col,block 每個一開始都可以填入1~9
    rowNum = [[1,2,3,4,5,6,7,8,9] for i in range(9)]
    colNum = [[1,2,3,4,5,6,7,8,9] for i in range(9)]
    blockNum = [[1,2,3,4,5,6,7,8,9] for i in range(9)]
    markKnown(board, rowNum, colNum, blockNum)
    #call recurion function
    fill(board, 0, rowNum, colNum, blockNum)
    
def main():
    findSol(list(map(int,input().split())))
    
if __name__ == '__main__':
    main()

### 測資

6 0 9 0 0 0 7 0 4 0 0 0 9 0 0 6 3 0 0 0 0 0 7 0 0 8 9 5 4 0 0 9 6 0 7 3 0 0 0 0 3 0 0 0 0 9 3 0 4 1 0 0 6 5 3 6 0 0 8 0 0 0 0 0 7 2 0 0 4 0 0 0 8 0 4 0 0 0 3 0 6