はじめに
数理最適化でナンプレ（数独）を解ければたいていのモデルは組めるんじゃない？という言葉を頂いたので、勉強がてら作ってみました。
モジュールインポート
まずはモジュールをインポートします
使うのはDataFrame用のpandas
そして数理最適化の心臓 pulp
from pulp import *
import pandas as pd
問題を読み込み
問題となるcsvを読み込みます
df_question = pd.read_csv(
"<dir>/numple_Q.csv",
names=('0', '1', '2', '3', '4', '5','6', '7', '8'),
header=None)
csvの中身はこんな感じ。
数理モデルを作成
数理モデルを作っていきます
LpProblem()の引数で最小化/最大化を決めます
sense=LpMinimize/LpMaximize
デフォルトは最小化になります
'''ナンプレ（数独）は条件を満たしていればよいので最小化/最大化は考慮不要'''
model = LpProblem()
変数を作成
変数xは0-1変数で考える
例えば、x[行][列][値]として、行0、列0のマスで考えた時、
1が入っているか否かを保持するx[0][0][1]
2が入っているか否かを保持するx[0][0][2]...のように、1マス当たり9のxが必要
ナンプレは9*9のマス数なので、列9*行9*値9=729の変数が必要になります
x = LpVariable('x_name') で変数xを作成できます。
また、
x = [LpVariable(x_name, cat=変数型) for i in range(作りたいxの数)] とすることで配列形式のx[]を変数として作成可能です。
- LpVariableのオプション
- 第1引数：変数名（必須）
- lowBound：変数の下限。デフォルトはNoneで下限なし
- upBound：変数の上限。デフォルトはNoneで上限なし
- cat：変数の種類
- ->LpContinuous : 連続変数 デフォルト
- LpBinary : 0-1変数
# i=縦, j=横, k=値
num_low=len(df_question.index)
num_col=len(df_question.columns)
num_num=9
x = [[[LpVariable('x:%s_%s_%s'%(i,j,k), cat=LpBinary) for k in range(num_num)] for j in range(num_col)] for i in range(num_low)]
目的関数を作成
ナンプレ（数独）は条件を満たしていればよいので目的関数はなし
制約条件を作成
model.setObjective(式) で制約式をモデルに追加できます。
x[]の合計を最大化したい場合は、model.setObjective(lpSum(x)) => x[0] + x[1] + … + x[-1]
x[]とa[]の内積の合計を最大化したい場合は、model.setObjective(lpDot(a, x)) => a[0] * x[0] + a[1] * x[1] + … + a[-1] * x[-1]
''' 1行の中に同じ数字が入ってはいけない
1行で考えた時、x[i][j][k]の[j]が変動する
x[0][0][1]+x[0][1][1]+.....x[0][8][1]=1
x[0][0][2]+x[0][1][2]+.....x[0][8][2]=1
:
x[1][0][1]+x[1][1][1]+.....x[1][8][1]=1
:
:
'''
for i in range(num_low):
for k in range(num_num):
model += lpSum(x[i][j][k] for j in range(num_col)) == 1
''' 1列の中に同じ数字が入ってはいけない
1列で考えた時、x[i][j][k]の[i]が変動する
x[0][0][1]+x[1][0][1]+.....x[8][0][1]=1
:
:
'''
for j in range(num_col):
for k in range(num_num):
model += lpSum(x[i][j][k] for i in range(num_low)) == 1
''' 3*3の中に同じ数字が入ってはいけない
x[0][0][1]+x[1][0][1]+x[2][0][1]+x[0][1][1]+x[1][1][1]+x[2][1][1]+x[0][2][1]+x[1][2][1]+x[2][2][1]=1
x[0][0][2]+x[1][0][2]+x[2][0][2]+x[0][1][2]+x[1][1][2]+x[2][1][2]+x[0][2][2]+x[1][2][2]+x[2][2][2]=1
:
x[3][0][1]+x[4][0][1]+x[5][0][1]+x[3][1][1]+x[4][1][1]+x[5][1][1]+x[3][2][1]+x[4][2][1]+x[5][2][1]=1
:
:
'''
for l in range(9):
for k in range(num_num):
model += lpSum(x[i][j][k] for j in range(num_col) for i in range(num_low) if (i//3)*3+j//3==l) == 1
''' 1マスには1つの数字のみが入る
x[0][0][1]+x[0][0][2]+.....x[0][0][9]=1
:
:
'''
for i in range(num_low):
for j in range(num_col):
model += lpSum(x[i][j][k] for k in range(num_num)) == 1
''' 既に数字が入っているところはその数字を使う
'''
for i in range(num_low):
for j in range(num_col):
for k in range(num_num):
if df_question.at[i, str(j)] == k+1:
model += lpSum(x[i][j][k]) == 1
ソルバーの実行
model.solve()
lpファイル出力
model.writeLP("test.lp")
結果をdfに格納する
df_result = pd.DataFrame(
columns=['0', '1', '2', '3', '4', '5','6', '7', '8'])
for i in range(num_low):
for j in range(num_col):
for k in range(num_num):
if pulp.value(x[i][j][k]) == 1 :
df_result.at[i, str(j)] = k+1
df_result.to_csv("<dir>/numple_R.csv", header=None, index=None)
csvで出力した結果はこんな感じ。
お疲れさまでした。