Pythonで唯一解の数独パズルを生成する方法

数独は9×9のグリッドに1から9までの数字を入れていくパズルで、各行・各列・各3×3ブロックに1〜9がちょうど1回ずつ現れるというルールがあります。一見単純ですが、プログラミングの題材としてはかなり奥が深く、とくに「唯一解を持つ数独パズルを生成する」処理は思ったより手強い課題です。

というのも、完成した盤面から適当に数字を消すだけでは、答えが複数存在する「壊れた問題」が簡単にできてしまうからです。良問の条件は、論理だけで唯一の答えにたどり着けること。この記事では、Pythonでそれを保証しながらパズルを生成する実装を紹介します。

処理の流れは次の3段階です。

1. 完全に埋まった有効な数独グリッドを生成する
2. セルを1つずつ空白にしていく
3. 空白にするたびに「解がまだ1つだけか」を確認し、複数解になるなら元に戻す

1. 完全な数独グリッドの生成

まずはバックトラッキング（行き詰まったら一手戻って別の候補を試す探索手法）で、完全に埋まった盤面を作ります。候補数字をシャッフルして試すことで、実行のたびに異なる盤面が得られます。

import random
import copy

def create_empty_grid():
    """空の数独グリッドを作成"""
    return [[0 for _ in range(9)] for _ in range(9)]

def is_valid(grid, row, col, num):
    """指定された位置に数字を置けるかチェック"""
    # 行のチェック
    for x in range(9):
        if grid[row][x] == num:
            return False

    # 列のチェック
    for x in range(9):
        if grid[x][col] == num:
            return False

    # 3x3ブロックのチェック
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if grid[i + start_row][j + start_col] == num:
                return False

    return True

def solve_sudoku(grid, row=0, col=0):
    """バックトラッキングでグリッドを解く"""
    if row == 9:
        return True

    if col == 9:
        return solve_sudoku(grid, row + 1, 0)

    if grid[row][col] != 0:
        return solve_sudoku(grid, row, col + 1)

    # 1-9の数字をランダムな順序で試す
    nums = list(range(1, 10))
    random.shuffle(nums)

    for num in nums:
        if is_valid(grid, row, col, num):
            grid[row][col] = num

            if solve_sudoku(grid, row, col + 1):
                return True

            grid[row][col] = 0

    return False

def generate_solved_grid():
    """解かれた数独グリッドを生成"""
    grid = create_empty_grid()
    solve_sudoku(grid)
    return grid

2. 唯一解を保ちながらセルを空白にする

ここが本題です。ポイントは「解の個数を数える関数」を用意すること。ただし全解を列挙する必要はなく、2つ見つかった時点で打ち切れば十分です（唯一解かどうかの判定には「1つか、2つ以上か」だけ分かればよいため）。この早期打ち切りで速度が大幅に改善します。

def count_solutions(grid):
    """数独の解の数を数える（最大2つまで）"""
    solutions = [0]

    def backtrack(row=0, col=0):
        if solutions[0] >= 2:
            return  # 2つ以上の解があれば終了

        if row == 9:
            solutions[0] += 1
            return

        if col == 9:
            backtrack(row + 1, 0)
            return

        if grid[row][col] != 0:
            backtrack(row, col + 1)
            return

        for num in range(1, 10):
            if is_valid(grid, row, col, num):
                grid[row][col] = num
                backtrack(row, col + 1)
                grid[row][col] = 0  # バックトラック

    backtrack()
    return solutions[0]

def generate_puzzle(difficulty='medium'):
    """難易度に応じたパズルを生成"""
    # 難易度ごとの空白セル数
    difficulty_levels = {
        'easy': 30,
        'medium': 40,
        'hard': 50,
        'expert': 60
    }

    cells_to_remove = difficulty_levels.get(difficulty, 40)

    # 解かれたグリッドを生成
    solved_grid = generate_solved_grid()
    puzzle = copy.deepcopy(solved_grid)

    # ランダムに選んだセルを空白にする
    cells = [(i, j) for i in range(9) for j in range(9)]
    random.shuffle(cells)

    for i, j in cells:
        # 元の値を保存
        temp = puzzle[i][j]
        puzzle[i][j] = 0

        # コピーを作成して解の数を数える
        grid_copy = copy.deepcopy(puzzle)

        # 唯一解でなければ元に戻す
        if count_solutions(grid_copy) != 1:
            puzzle[i][j] = temp

        # 目標の空白セル数に達したら終了
        if sum(row.count(0) for row in puzzle) >= cells_to_remove:
            break

    return puzzle, solved_grid

セルを消すたびに解の個数を確認し、複数解になってしまう場合はその数字を戻す——この繰り返しにより、生成されるパズルは常に唯一解が保証されます。

3. パズルの表示と実行

最後に、盤面をコンソールに見やすく出力する関数と、難易度を選んで実行するメイン処理です。

def print_grid(grid):
    """グリッドを見やすく表示"""
    for i in range(9):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - -")

        for j in range(9):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(grid[i][j] if grid[i][j] != 0 else " ")
            else:
                print(str(grid[i][j] if grid[i][j] != 0 else " ") + " ", end="")

def main():
    """メイン関数"""
    difficulties = ['easy', 'medium', 'hard', 'expert']
    print("難易度を選択してください:")
    for i, diff in enumerate(difficulties, 1):
        print(f"{i}. {diff}")

    choice = input("選択（1-4）: ")
    try:
        difficulty = difficulties[int(choice) - 1]
    except (ValueError, IndexError):
        difficulty = 'medium'  # デフォルト

    print(f"\n{difficulty}難易度の数独パズルを生成中...")
    puzzle, solution = generate_puzzle(difficulty)

    print("\n問題:")
    print_grid(puzzle)

    print("\n解答:")
    print_grid(solution)

if __name__ == "__main__":
    main()

実行すると、難易度を選ぶプロンプトのあとに問題と解答のペアが出力されます。生成した問題の検算には、当サイトの数独ソルバーに入力してみるのも手軽でおすすめです。

改良のアイデア

このコードは動く最小構成なので、伸びしろがたくさんあります。

• 難易度評価の精密化：空白セルの数だけでなく、解くのに必要なテクニック（隠れペア、X-Wingなど）で難易度を判定する。人間が感じる難しさに近づきます
• 盤面の対称性：市販の数独のように、ヒント配置を点対称にすると見た目が美しくなります
• 高速化：copy.deepcopy の多用がボトルネックになるので、消したセルだけ戻す差分方式にすると大幅に速くなります
• GUI化：tkinterやWebフロントエンドを付けて遊べるようにする

数独生成はバックトラッキングやDFSといった探索アルゴリズムの練習台として最適です。自作ジェネレーターが完成したら、人間の腕試しとして当サイトの今日の20問やエキスパート問題と解き比べてみてください。自分のプログラムが作った問題の「クセ」が見えてきて面白いですよ。