Leetcode題解 Python： Sudoku Solver

解數獨，非常地生活化。

這跟上一個 N-Queens 不同，你要直接修改數獨表，最後要是已經完成的狀態，這次要把答案紀錄好就不再刪除了。

而且一排排往下的概念並不好用，因為有些已經填滿了。

先把主架構寫出來，寫出一個回溯法函數(Backtracking)，把排換個概念換成層，而每一層就是單一個還沒下過的位置，靠著遍歷數獨表就可以知道有哪些位置。

接者就可以 Backtrack 一路往下搜尋。

當順利解出來時，就不會再有下一層，這時會出現報錯，出現別的情況，只要當這個情況出現時，回傳一個值，就可以用回傳值判斷要不要刪掉最後下過的位置，這樣就能阻止刪掉解法的最後一步。

class Solution:
    def solveSudoku(self, board) -> None:
        """
        Do not return anything, modify board in-place instead.
        """     
        def getCandidate(y, x):            
            Candidates = {}.fromkeys([str(i) for i in range(1,10)])            
            for x2 in range(9):                
                if board[y][x2] in Candidates: del Candidates[board[y][x2]]
            for y2 in range(9):                
                if board[y2][x] in Candidates: del Candidates[board[y2][x]]     
            for y2 in range(y//3*3, y//3*3+3):
                for x2 in range(x//3*3, x//3*3+3):
                    if board[y2][x2] in Candidates: del Candidates[board[y2][x2]]
            return Candidates.keys()             

        def nextStep(level):
            try:
                row, col, _ = stepPos[level]
                for num in getCandidate(row, col):
                    board[row][col] = num                  
                    if nextStep(level+1): 
                        return True
                    else:
                        board[row][col] = "." 
            except:
                return True

        stepPos = []  
        for y in range(9):
            for x in range(9): 
                if board[y][x] == ".":
                    stepPos.append((y, x, len(getCandidate(y, x))))

        stepPos.sort(key=lambda x: x[2])
        nextStep(0)

當中多了一作法，在找出所有可下位置時算出可能的數字數，接著再用可能數字數從小到大排序，就會從最少可能組合開始下起，這就像我們玩數獨一般，會從最少可能性的地方找起。

一看可以優化，用memo紀錄各col各row各area的所有數字，這樣用 in 找值的時候，能夠最快效率。

沒有排序問題，也沒有設值需求，然後需要求出兩數組差(123456789 與 各col各row各area)，所以使用集合 set ，這樣就能方便計算。

剛好可以安插在找所有可下位置的時候，將各col各row各area的所有數字都添加進去。

class Solution:
    def solveSudoku(self, board) -> None:
        """
        Do not return anything, modify board in-place instead.
        """     
        Candidates = {*'123456789'}
        memoCol = {}
        memoRow = {}
        memoArea = {}
        for i in range(9):
            memoCol[i] = set()
            memoRow[i] = set()
            memoArea[i] = set()

        def getCandidate(y, x):            
            return Candidates - memoArea[x//3+y//3*3] - memoCol[x] - memoRow[y]          

        def nextStep(level):
            try:
                row, col = stepPos[level]
                for num in getCandidate(row, col):
                    memoCol[col].add(num)   
                    memoRow[row].add(num)    
                    memoArea[col//3+row//3*3].add(num)   
                    board[row][col] = num                
                    if nextStep(level+1): 
                        return True
                    else:
                        board[row][col] = "."                   
                        memoCol[col].discard(num)
                        memoRow[row].discard(num)
                        memoArea[col//3+row//3*3].discard(num)
            except:
                return True

                
        stepPos = []  
        for y in range(9):
            for x in range(9): 
                v = board[y][x]
                if v == ".":
                    stepPos.append((y,x))
                else:   
                    memoCol[x].add(v)       
                    memoRow[y].add(v)   
                    memoArea[x//3+y//3*3].add(v)   

        nextStep(0)