組合せ最適化でカックロを解く #Python

Advent Calendar 1日目の記事数独を通して組合せ最適化を学ぼう
Advent Calendar 3日目の記事組合せ最適化でボンバーパズルを解く

これなに

カックロ¹を、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。

自分でも試してみたい人は、下記を参考にしてください。

数独を通して組合せ最適化を学ぼう

問題

下図の白いマスに1~9の数字を入れて、縦または横の合計がヒントと同じになるようにします。

Pythonでは、data（.ならば数字のマス）、hint_v（縦の合計）、hint_h（横の合計）を使うことにします。

python

import re, pandas as pd
from pulp import LpProblem, lpDot, lpSum, value
from ortoolpy import addbinvars
data = """\
#..##
....#
..#..
#....
##..#""".splitlines()
hint_v = [ # 開始行、開始列、個数、合計
    (0,1,4,11),
    (0,2,2,4),
    (1,0,2,14),
    (1,3,4,10),
    (2,4,2,3),
    (3,2,2,3),
]
hint_h = [ # 開始行、開始列、個数、合計
    (0,1,2,5),
    (1,0,4,17),
    (2,0,2,6),
    (2,3,2,4),
    (3,1,4,10),
    (4,2,2,3),
]

変数表

下記のような変数表を作成します。各行の変数は0または1をとります。
変数の値が1ならば、該当行該当列のマスが該当の数になります。

	行	列	数	Var
0	0	1	1	v000001
1	0	1	2	v000002
...	...	...	...	...

python

ni,nj = len(data),len(data[0])
a = pd.DataFrame([(i,j,k) for i in range(ni) for j in range(nj)
    if data[i][j]=='.' for k in range(1,10)], columns=list('行列数'))
a['Var'] = addbinvars(len(a))
a[:2]

数理モデルを作り解く

変数表ができたので、カックロの解になるように、制約条件を追加し数理モデルを作成し、解きましょう。

各マスに数字を1つ入れる。 …(1)
- for _,v in a.groupby(('行','列'))で1つのマスの変数がDataFrameのvに入るので、m += lpSum(v.Var) == 1とすれば、数字を1つ選ぶことになります。
一連の並びで、同じ数字は1つまで。 …(2)
- 下記では、一連の並びをDataFrame(b)に入れています。一連の並びは、長方形なので、DataFrame.queryで簡単に取り出せます。
一連の並びの合計をヒントと同じに。 …(3)
- 2列のDataFrameの各列を、それぞれ第1引数、第2引数に渡したいとき、*b.T.valuesでできます。これは、転置（T）してnumpy.array（values）にして展開（*）しています。

python

m = LpProblem()
for _,v in a.groupby(('行','列')):
    m += lpSum(v.Var) == 1 # (1)
for (di,dj),hint in zip([(1,0),(0,1)],[hint_v,hint_h]):
    for si,sj,nl,sm in hint:
        b = a.query(f'{si}<=行<={si+nl*di}&{sj}<=列<={sj+nl*dj}')[['数','Var']]
        for _,v in b.groupby('数'):
            m += lpSum(v.Var) <= 1 # (2)
        m += lpDot(*b.T.values) == sm # (3)
m.solve()

結果の表示

python

a['Val'] = a.Var.apply(value)
r = a[a.Val>0.5].数[::-1].tolist()
print(re.sub('\\.', lambda _: str(r.pop()), '\n'.join(data)))
>>>
#23##
9512#
51#31
#3142
##21#

解けていることが確認できます。

以上

カックロは株式会社二コリの登録商標です。 ↩