Python是一種流行的編程語言,可以非常方便地解決許多問題,例如解決數獨這樣的問題。下面介紹一個基于Python的數獨求解程序。
class SudokuSolver: # 初始化數獨棋盤 def __init__(self, bo): self.board = bo # 判斷數獨棋盤是否有效 def _is_valid(self, row, col, val): # 檢查行 for i in range(9): if self.board[row][i] == val: return False # 檢查列 for i in range(9): if self.board[i][col] == val: return False # 檢查3X3宮格 row_start = (row // 3) * 3 col_start = (col // 3) * 3 for i in range(row_start, row_start + 3): for j in range(col_start, col_start + 3): if self.board[i][j] == val: return False return True # 空格遞歸搜索并填充數獨棋盤 def solve(self): for row in range(9): for col in range(9): if self.board[row][col] == 0: for val in range(1, 10): if self._is_valid(row, col, val): self.board[row][col] = val if self.solve(): return True self.board[row][col] = 0 return False return True
上面的代碼定義了一個SudokuSolver類,其中包含三個方法:__init__、_is_valid和solve。__init__用于初始化數獨棋盤,_is_valid用于判斷數獨棋盤中某個位置是否可以放置某個數字,solve方法則是用于搜索和填充數獨棋盤。
如果想要使用上面的程序解決數獨問題,可以先定義一個數獨棋盤,然后將其傳入到SudokuSolver類的構造函數中。
# 定義數獨棋盤 board = [ [5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0, 0, 6], [0, 6, 0, 0, 0, 0, 2, 8, 0], [0, 0, 0, 4, 1, 9, 0, 0, 5], [0, 0, 0, 0, 8, 0, 0, 7, 9] ] # 創建數獨棋盤求解器 solver = SudokuSolver(board) # 求解數獨棋盤 if solver.solve(): for row in board: print(row) else: print("No solution exist.")
上面的代碼中就演示了如何使用上面定義的SudokuSolver類來解決數獨問題。只需要將數獨棋盤傳入SudokuSolver類的構造函數,然后調用solve方法即可。