Advent Calendar 11日目の記事組合せ最適化でスターバトルを解く
Advent Calendar 13日目の記事組合せ最適化でペイントエリアを解く

これなに

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

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

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

問題

3つの組(kinds)を入力し、各組間の対応を求めます。
ヒント(data)
- 明は白いのを買った。
- 明は糸じゃない。
- 青い紙を買った人がいる。
- 勇は紙じゃない。
- 正は靴を買った。
- 正は赤じゃない。

Pythonでは、kinds（3つの種類）、data（成否、人、物、色）を使うことにします。

python

import pandas as pd
from pulp import LpProblem, lpSum, value
from itertools import chain, product
from ortoolpy import addbinvar
kinds = [['明','勇','正','洋'],
         ['傘','靴','紙','糸'],
         ['赤','青','白','黒']]
data = [s.split(',') for s in """\
1,明,,白
0,明,糸,
1,,紙,青
0,勇,紙,
1,正,靴,
0,正,,赤""".splitlines()]

変数表

下記のような変数表を作成します。各行の変数(Var)は0または1をとります。
変数の値が1ならば、該当の人、物、色が成立します。

	人	物	色	Var
0	明	傘		v000001
1	明	靴		v000002
...	...	...	...	...

python

a1 = pd.DataFrame((s0,s1,'',addbinvar()) for s0,s1 in product(kinds[0],kinds[1]))
a2 = pd.DataFrame((s0,'',s2,addbinvar()) for s0,s2 in product(kinds[0],kinds[2]))
a3 = pd.DataFrame(('',s1,s2,addbinvar()) for s1,s2 in product(kinds[1],kinds[2]))
a = pd.concat([a1,a2,a3])
a1.columns = a2.columns = a3.columns = a.columns = ['人','物','色','Var']
a[:2]

数理モデルを作り解く

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

縦横で丸は1つ。
AかつB、BかつCなら、CかつA。
ヒントを満たすこと。

python

m = LpProblem()
for a0,c1,c2 in [(a1,'人','物'),(a2,'人','色'),(a3,'物','色')]:
    for _,v in chain(a0.groupby(c1),a0.groupby(c2)):
        m += lpSum(v.Var) == 1
for s1,s2,s3 in product(*kinds):
    vlst = [a1.query(f'人=="{s1}"&物=="{s2}"').Var.iloc[0],
            a2.query(f'人=="{s1}"&色=="{s3}"').Var.iloc[0],
            a3.query(f'物=="{s2}"&色=="{s3}"').Var.iloc[0]]
    for v in vlst:
        m += lpSum(vlst) <= 1+2*v
for c,s1,s2,s3 in data:
    m += a.query(f'人=="{s1}"&物=="{s2}"&色=="{s3}"').Var.iloc[0] == int(c)
m.solve()

結果の表示

python

a1['Val'] = a1.Var.apply(value)
a2['Val'] = a2.Var.apply(value)
a1.loc[a1.Val>0.5,['人','物']].merge(a2.loc[a2.Val>0.5,['人','色']])

	人	物	色
0	明	傘	白
1	勇	糸	赤
2	正	靴	黒
3	洋	紙	青

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

以上

推理パズルは株式会社二コリの登録商標です。 ↩