はじめに

数理最適化でナンプレ（数独）を解ければたいていのモデルは組めるんじゃない？という言葉を頂いたので、勉強がてら作ってみました。

モジュールインポート

まずはモジュールをインポートします
使うのは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で出力した結果はこんな感じ。

お疲れさまでした。