組合せ最適化で推理パズルを解く

Advent Calendar 11日目の記事 [組合せ最適化でスターバトルを解く](https://qiita.com/SaitoTsutomu/items/8bc6342225a63fb68888)
Advent Calendar 13日目の記事 [組合せ最適化でペイントエリアを解く](https://qiita.com/SaitoTsutomu/items/5815c64ec23b8c88eee0)

## これなに

**推理パズル**[^1]を、Pythonで[組合せ最適化](https://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721)モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。

[^1]: 推理パズルは[株式会社二コリ](http://nikoli.co.jp/)の[登録商標](http://www.nikoli.co.jp/ja/copyright/)です。

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

- [数独を通して組合せ最適化を学ぼう](https://qiita.com/SaitoTsutomu/items/bd09190d8a02432b3f16)

## 問題

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

![](https://raw.githubusercontent.com/SaitoTsutomu/opt4puzzle/master/pic/suiri.png)

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

```py3: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ならば、該当の人、物、色が成立します。

<table><tr><th></th><th>人</th><th>物</th><th>色</th><th>Var</th></tr>
<tr><th>0</th><td>明</td><td>傘</td><td></td><td>v000001</td></tr>
<tr><th>1</th><td>明</td><td>靴</td><td></td><td>v000002</td></tr>
<tr><th>...</th><td>...</td><td>...</td><td>...</td><td>...</td></tr>
</table>

```py3: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。
- ヒントを満たすこと。

```py3: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()
```

### 結果の表示

```py3: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,['人','色']])
```

<table>
  <thead>
    <tr>
      <th></th>
      <th>人</th>
      <th>物</th>
      <th>色</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>明</td>
      <td>傘</td>
      <td>白</td>
    </tr>
    <tr>
      <th>1</th>
      <td>勇</td>
      <td>糸</td>
      <td>赤</td>
    </tr>
    <tr>
      <th>2</th>
      <td>正</td>
      <td>靴</td>
      <td>黒</td>
    </tr>
    <tr>
      <th>3</th>
      <td>洋</td>
      <td>紙</td>
      <td>青</td>
    </tr>
  </tbody>
</table>

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

以上