Python で数独を解く

数独ソルバーの作成は、再帰的バックトラッキングとアルゴリズム解決に慣れるのに最適な方法です。このブログ投稿では、これらのメソッドをデモンストレーションするために私が作成したコマンドライン Sudoku ゲーム プロジェクトのいくつかのヘルパー関数を検討します。このファイルには、数独パズルの解決を容易にする重要なヘルパー関数が含まれています。主要な関数 is_valid、find_empty、solve に分けて説明します。

番号の有効性をチェックする
is_valid 関数は、指定されたセルに特定の数値を配置することが Sudoku ルールに従って有効かどうかをチェックします。

def is_valid(board, row, col, num):
    # Check if the number is not present in the same row and column
    if num in board[row] or num in [board[i][col] for i in range(9)]:
        return False

    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False
    return True

行と列のチェック: 数値が同じ行または列に存在しないことを確認します。
サブグリッド チェック: 番号が 3x3 サブグリッドに存在しないことを確認します。

空のセルを見つける

find_empty 関数は、ボード上の次の空のセル (0 で表される) を見つけます。

def find_empty(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

反復: ボードを反復処理して空のセルを見つけます。
Return: 最初に見つかった空のセルの座標を返します。ボードがいっぱいの場合は None を返します。

数独パズルを解く

ソルブ機能はバックトラッキングを使用して数独パズルを解きます。

def solve(board):
    empty_cell = find_empty(board)
    # Board is solved
    if not empty_cell:
        return board

    row, col = empty_cell

    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    random.shuffle(numbers)

    for num in numbers:
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve(board):
                return board
            # Backtrack if current placement doesn't lead to a solution
            board[row][col] = 0
        # No valid number for current empty cell
    return False

空のセルを検索: find_empty を使用して次の空のセルを見つけます。
バックトラッキング: is_valid で有効性をチェックしながら、空のセルに 1 ～ 9 の数字を配置しようとします。

再帰的解決: ボードを再帰的に解決しようとします。配置が解決策につながる場合は、解決されたボードが返されます。
バックトラック: 配置が解決策につながらない場合は、セルをリセットして次の番号を試します。

結論

ヘルパー関数は、Sudoku ソルバーの機能にとって非常に重要です。 is_valid 関数は数独ルールに従っていることを保証し、find_empty は次に埋めるセルを見つけるのに役立ち、solve は再帰的バックトラッキングを使用して解を見つけます。これらのヘルパー関数を理解すると、数独パズルをプログラムで解く背後にあるロジックについての洞察が得られます。

以上がPython で数独を解くの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。