數獨算法是一個非常經典的問題,也是計算機科學中的一個重要的算法問題。在這個問題中,我們需要填入一個 9x9 的網格,使得每一行、每一列和每一個 3x3 的子網格中,數字 1~9 都只出現一次。
# Python 數獨算法 def solve_sudoku(grid): # 首先,使用 backtracking 方法解決數獨問題 for row in range(9): for col in range(9): if grid[row][col] == 0: for num in range(1, 10): if is_valid(grid, row, col, num): grid[row][col] = num if solve_sudoku(grid): return True grid[row][col] = 0 return False return True def is_valid(grid, row, col, num): # 檢查同一行、同一列和同一 3x3 的子網格上是否出現了相同的數 for i in range(9): if grid[row][i] == num or grid[i][col] == num: return False start_row = (row // 3) * 3 start_col = (col // 3) * 3 for i in range(start_row, start_row + 3): for j in range(start_col, start_col + 3): if grid[i][j] == num: return False return True
在這里,我們使用了 backtracking 方法來解決數獨問題。這種方法是一個很常見的搜索算法,它通過不斷嘗試可能的解決方案,直到找到一個正確的解決方案為止。
對于每一個未填的格子,我們遍歷 1~9 中的每一個數字,然后檢查當前數字是否合法,如果合法,就填入這個數字,然后繼續嘗試填下一格。如果我們最終找到了一個正確的解決方案,那么我們就返回 True,如果找不到正確的解決方案,就返回 False。
在填數字的過程中,我們還需要檢查當前填入的數字是否合法。我們需要檢查同一行、同一列和同一 3x3 的子網格上是否出現了相同的數,如果出現了相同的數,那么填入這個數字是不合法的。
最終,我們可以通過調用 solve_sudoku 函數來解決數獨問題,這個函數會返回一個表示解決方案的 2D 數組。