数理最適化でナンプレ（数独）を解く

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


# モジュールインポート
まずはモジュールをインポートします
使うのはDataFrame用のpandas
そして数理最適化の心臓 **pulp**
~~~Python
from pulp import *
import pandas as pd
~~~

# 問題を読み込み
問題となるcsvを読み込みます
~~~Python
df_question = pd.read_csv(
    "<dir>/numple_Q.csv",
    names=('0', '1', '2', '3', '4', '5','6', '7', '8'),
    header=None)
~~~


csvの中身はこんな感じ。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2822713/491e9803-9389-097d-a8a1-1b89a37681ee.png)

















# 数理モデルを作成
数理モデルを作っていきます

LpProblem()の引数で最小化/最大化を決めます
　sense=LpMinimize/LpMaximize
デフォルトは最小化になります

~~~Python
'''ナンプレ（数独）は条件を満たしていればよいので最小化/最大化は考慮不要'''
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[]を変数として作成可能です。




<dl>
  <dt>LpVariableのオプション</dt>
  <dd>第1引数：変数名（必須）</dd>
  <dd>lowBound：変数の下限。デフォルトはNoneで下限なし</dd>
  <dd>upBound：変数の上限。デフォルトはNoneで上限なし</dd>
  <dd>cat：変数の種類</dd>
  <dd>　　->LpContinuous : 連続変数 デフォルト</dd>
  <dd>　　　LpBinary : 0-1変数</dd>
</dl>

~~~Python
# 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]

~~~Python
''' 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
~~~

# ソルバーの実行
~~~Python
model.solve()
~~~
# lpファイル出力
~~~Python
model.writeLP("test.lp")
~~~


# 結果をdfに格納する
~~~Python
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で出力した結果はこんな感じ。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2822713/50e0ac99-7c01-9fc4-eb35-e27d9b927094.png)


お疲れさまでした。