(2026/07/27)
数独を計算する
データ
[4, , , 2, , 1, , , 7]
[1, , , , , , , , 3]
[, , 8, , 7, , 4, , ]
[, 2, , 5, , 4, , 6, ]
[, 4, , , , , , 5, ]
[, 8, , 3, , 2, , 9, ]
[, , 9, , 1, , 2, , ]
[6, , , , , , , , 1]
[5, , , 4, , 8, , , 6]
0-1 整数計画法を使用して数独パズルを解く
データ行列 B を以下に示します。
最初の行 B(1,1,4) は 1 行 1 列目にヒント 4 が表示されていることを意味します。
B = [1,1,4;
1,4,2;
1,6,1;
1,9,7;
2,1,1;
2,9,3;
3,3,8;
3,5,7;
3,7,4;
4,2,2;
4,4,5;
4,6,4;
4,8,6;
5,2,4;
5,8,5;
6,2,8;
6,4,3;
6,6,2;
6,8,9;
7,3,9;
7,5,1;
7,7,2;
8,1,6;
8,9,1;
9,1,5;
9,4,4;
9,6,8;
9,9,6];
プログラムコード
# 数独を完璧に解くための「0-1整数計画法」プログラム
!pip install -q pulp
import pulp
# 文字列からヒントデータを復元します（消去バグを回避するため）
hint_text = """
1,1,4; 1,4,2; 1,6,1; 1,9,7;
2,1,1; 2,9,3;
3,3,8; 3,5,7; 3,7,4;
4,2,2; 4,4,5; 4,6,4; 4,8,6;
5,2,4; 5,8,5;
6,2,8; 6,4,3; 6,6,2; 6,8,9;
7,3,9; 7,5,1; 7,7,2;
8,1,6; 8,9,1;
9,1,5; 9,4,4; 9,6,8; 9,9,6
"""
# テキストからデータを読み込んでリストを作成
B = []
for item in hint_text.replace('\n', '').split(';'):
if item.strip():
row, col, val = map(int, item.split(','))
B.append([row, col, val])
# 2. 数理モデルの作成（0-1整数計画法）
prob = pulp.LpProblem("Sudoku_Solver", pulp.LpMinimize)
# 729個の0-1変数を作成 (x[i, j, k])
choices = pulp.LpVariable.dicts("Choice", (range(1, 10), range(1, 10), range(1, 10)), cat="Binary")
# 3. 方程式（制約条件）の自動組み立て
# (1) 各マスには数字が1つだけ入る
for i in range(1, 10):
for j in range(1, 10):
prob += pulp.lpSum([choices[i][j][k] for k in range(1, 10)]) == 1
# (2) 各行に同じ数字は1つだけ
for i in range(1, 10):
for k in range(1, 10):
prob += pulp.lpSum([choices[i][j][k] for j in range(1, 10)]) == 1
# (3) 各列に同じ数字は1つだけ
for j in range(1, 10):
for k in range(1, 10):
prob += pulp.lpSum([choices[i][j][k] for i in range(1, 10)]) == 1
# (4) 3x3のブロック内に同じ数字は1つだけ
for r in range(3):
for c in range(3):
for k in range(1, 10):
prob += pulp.lpSum([choices[i][j][k] for i in range(r*3+1, r*3+4) for j in range(c*3+1, c*3+4)]) == 1
# (5) 既に入っている初期ヒント (データ行列B) を固定
for hint in B:
prob += choices[hint[0]][hint[1]][hint[2]] == 1
# 4. 計算開始（ソルバー実行）
prob.solve(pulp.PULP_CBC_CMD(msg=False))
# 5. 結果のきれいに表示
print("【数独の正しい解】\n")
for i in range(1, 10):
row_vals = []
for j in range(1, 10):
for k in range(1, 10):
if pulp.value(choices[i][j][k]) == 1:
row_vals.append(str(k))
print(" ".join(row_vals))
Google Python
https://colab.research.google.com/
左上の [ノートブックを新規作成]
入力エリアに、以下のプログラムコードを丸ごとコピー＆ペースト
枠のすぐ左側にある [再生ボタン（◯の中に▶のマーク）] をクリック
画面の下部に重複が一切ない本物の正しい答えがズラリと表示
回答
[4, 9, 3, 2, 5, 1, 6, 8, 7]
[1, 6, 7, 8, 4, 9, 5, 2, 3]
[2, 5, 8, 6, 7, 3, 4, 1, 9]
[3, 2, 1, 5, 9, 4, 7, 6, 8]
[9, 4, 6, 1, 8, 7, 3, 5, 2]
[7, 8, 5, 3, 6, 2, 1, 9, 4]
[8, 3, 9, 7, 1, 6, 2, 4, 5]
[6, 7, 4, 9, 2, 5, 8, 3, 1]
[5, 1, 2, 4, 3, 8, 9, 7, 6]
（※ソルバーの内部アルゴリズムにより、空欄の埋め方にわずかなバリエーションが出る場合がありますが、縦・横・3×3のすべてで1〜9が1回ずつしか登場しない完璧な配置になっています）
（参考）
Googleドライブに
Colab Notebook＞Untitled.ipynb
が自動生成される。
|