Sudokuは、数字を配置することによって空白の9x9グリッドを満たすパズルです。Pythonを使用して、Sudokuパズルを解く方法を学ぶことができます。

バックトラッキングアルゴリズム

Sudokuパズルを解くために使用できる一般的なアルゴリズムは、バックトラッキングです。これは、解答候補を網羅的に試し、問題が発生した場合は、前のステップに戻って新しい解答を試す方法です。

Pythonコード

Pythonコードでは、再帰関数を使用してバックトラッキングアルゴリズムを実装することができます。以下は、Sudokuパズルを解くためのPythonコードの例です。

def solve_sudoku(grid):
    find = find_empty(grid)
    if not find:
        return True
    else:
        row, col = find

    for i in range(1, 10):
        if valid(grid, i, (row, col)):
            grid[row][col] = i

            if solve_sudoku(grid):
                return True

            grid[row][col] = 0

    return False

def valid(grid, num, pos):
    # 行をチェック
    for i in range(len(grid[0])):
        if grid[pos[0]][i] == num and pos[1] != i:
            return False

    # 列をチェック
    for i in range(len(grid)):
        if grid[i][pos[1]] == num and pos[0] != i:
            return False

    # ボックスをチェック
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if grid[i][j] == num and (i,j) != pos:
                return False

    return True

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

使用方法

Sudokuパズルを解くには、以下のように呼び出すことができます。

# 空のセルを0で表現し、9x9グリッドのリストとしてパズルを入力する
puzzle = [
    [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
4,0,0,9,0,0,0,8,0],
    [0,0,0,0,8,0,0,7,9]
]

solve_sudoku(puzzle)

# 解答を出力する
for row in puzzle:
    print(row)

出力:

[
 [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]
]

このコードを使用して、Sudokuパズルを解くことができます。