組合せ最適化でチョコナを解く #Python

Advent Calendar 8日目の記事組合せ最適化でのりのりを解く
Advent Calendar 10日目の記事組合せ最適化でクリークを解く

これなに

チョコナを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。

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

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

問題

国(太線で区切られた部分)の数は、国内の黒マスの合計とする。国の数がない場合はいくつでもよい。
黒マスの連なりは、長方形とする。

下図の薄いグレーが解です。

Pythonでは、data（黒マスの数）、area（国のグループ）を使うことにします。

python

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
3.3...
.1....
22.21.
......
....3.
.2....""".splitlines()
area = """\
001111
022222
345677
345677
355899
3aa889""".splitlines()

変数表

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

	行	列	字	国	Var
0	0	0	3	0	v000001
1	0	1	0	0	v000002
...	...	...	...	...	...

python

ni, nj = len(data), len(data[0])
a = pd.DataFrame([(i,j,data[i][j],area[i][j]) for i in range(ni)
    for j in range(nj)], columns=list('行列字国'))
a.字 = a.字.apply(lambda c: int(c) if c.isdigit() else 0)
a['Var'] = addbinvars(len(a))
a[:2]

数理モデルを作り解く

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

各国の黒の数を指定した数に。
- 数字は1つだけなので、合計をとれます。注意点として、合計が0なら制約条件にしないことです。
黒の形を長方形にする。
- 任意の2x2の4マスの黒の合計が3にならないということです。
- 合計を3にしてはいけないという制約条件は、「4マスの黒の合計 <= 2+2*1マスの黒の合計」を4マスの中の各マスで見れば、OKです。
  - 何故なら、3のときだけ、「3<=2」という状態が出て成り立たないためです。

python

m = LpProblem()
for g,v in a.groupby('国'):
    if v.字.sum():
        m += lpSum(v.Var) == v.字.sum()
for i in range(ni-1):
    for j in range(nj-1):
        v = a.query(f'{i}<=行<={i+1}&{j}<=列<={j+1}').Var
        for x in v:
            m += lpSum(v) <= 2+2*x
m.solve()

結果の表示

python

a['Val'] = a.Var.apply(value)
plt.imshow((a.Val<0.5).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()

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

以上