こんにちは、エンジニアの皆さん！今日は自分の趣味プロジェクトで最近取り組んでいた、Pythonを使った数独パズルの生成について共有したいと思います。
数独は9×9のグリッドに1から9までの数字を入れていくパズルで、各行・各列・各3×3ブロックに1〜9の数字がそれぞれ一回ずつ使われるというルールがあります。単純そうに見えて奥が深く、プログラミング的にも興味深い課題がたくさんあります。
特に「唯一解を持つ数独パズル」を生成するのは、思ったより複雑なタスクでした。今回はその実装方法を紹介します。
数独パズル生成の基本的なアプローチ
数独パズルを生成する基本的な流れは次のようになります：
- 完全に解かれた有効な数独グリッドを生成する
- いくつかのセルを空白にして、パズルを作る
- パズルが唯一解を持つことを確認する
それでは、実装を見ていきましょう。
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 grid2. パズルの作成（セルを空白にする）
次に、完成したグリッドからいくつかのセルを空白にしてパズルを作ります。ただし、唯一解を保つため、慎重に空白を選ぶ必要があります。
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_grid3. 数独パズルの表示と使用方法
最後に、生成したパズルを表示して使えるようにしましょう。
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)
print("\n数独パズルを楽しんでください！")
if __name__ == "__main__":
main()実行結果の例
このコードを実行すると、次のような出力が得られます：
難易度を選択してください:
1. easy
2. medium
3. hard
4. expert
選択（1-4）: 2
medium難易度の数独パズルを生成中...
問題:
8 7 | 5 | 3 1
5 3 | 1 | 6
| 3 6 | 5 7 8
- - - - - - - - - - - -
8 5 | 3 | 2
| |
1 | 4 | 3 5
- - - - - - - - - - - -
4 5 1 | 8 6 |
7 | 5 | 8 4 3
2 3 | 7 4 | 6 5
解答:
2 8 7 | 6 5 9 | 3 1 4
5 3 4 | 1 7 8 | 2 6 9
1 9 6 | 3 6 2 | 5 7 8
- - - - - - - - - - - -
8 6 5 | 9 1 3 | 4 2 7
3 4 2 | 8 6 7 | 1 9 6
7 1 9 | 4 2 5 | 3 8 5
- - - - - - - - - - - -
4 5 1 | 2 8 6 | 7 3 9
9 7 8 | 5 4 1 | 8 4 3
6 2 3 | 7 9 4 | 6 5 1まとめ
今回紹介したコードでは、バックトラッキングアルゴリズムを使って：
- 完全な数独グリッドを生成
- 難易度に応じた空白セルの数を調整
- 唯一解を持つことを確認しながら、パズルを作成
という一連の処理を行っています。
数独パズルの生成は、アルゴリズムの学習や実装の練習に最適な題材です。特にバックトラッキングやDFSなどの探索アルゴリズムの理解が深まるでしょう。
さらに改良点として：
- パズルの対称性を確保する
- 難易度の評価をより精密にする（単純な空白セル数ではなく、解法テクニックの難しさで判定）
- GUIを追加して遊べるようにする
などが考えられます。
ぜひこのコードを基に、自分なりの数独ジェネレーターを作ってみてください。質問やフィードバックがあれば、コメント欄でお待ちしています！
