主題

LeetCode - 37. Sudoku Solver 解題心得

Not In My Back Yard | 2021-05-09 00:00:13 | 巴幣 0 | 人氣 17

題目連結:


題目意譯:
撰寫一個程式將空格填上數字並解出數獨謎題。

一個數獨的解應滿足以下所有規則:
每個數字 1 ~ 9 應出現在每列中恰好一次。
每個數字 1 ~ 9 應出現在每行中恰好一次。
每個數字 1 ~ 9 應出現在每個 3 × 3 子網格中恰好一次。

'.' 字元代表著空格子。

限制:
board.length == 9
board[i].length == 9
board[i][j] 為數字或是 '.'。
保證輸入的版面只有唯一解。



範例測資:
輸入: board = [["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"]]
輸出: [["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"]]
解釋: 輸入版面如上,而唯一解如下圖所示:


解題思維:
參見這題。而且本題最後不用特別地去判斷遞迴的結果有沒有找到解,因為題目保證了一定有解。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作