Advent Calendar 13日目の記事組合せ最適化でペイントエリアを解く
Advent Calendar 15日目の記事組合せ最適化でののぐらむを解く

これなに

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

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

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

問題

数字が記入されているマスからその数字の数だけ縦と横に線を引きます
1つのマスには1本の線しか引くことができません
数字が記入されているマスには線を引くことができません

下記は、左が問題で、右が答えです。

dataにヒントの数が入っているとします。

python

import pandas as pd
from itertools import product
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvars, addbinvars
data = """\
4..1..
.4..2.
..2..2
1..1..
.1..1.
..3..2""".split()

変数表

下記のような変数表を作成します。各行の変数は0または1をとります。
変数の値が1ならば、該当行該当列のマスが黒になります。
「向」は{0:左, 1:上, 2:右, 3:下}です。VDirはその方向かどうか、VLenは矢印の長さです。

	行	列	向	VDir	VLen
0	0	0	0	v000001	v000145
1	0	0	1	v000002	v000146
...	...	...	...	...	...

python

ni, nj = len(data), len(data[0])
mx = max(ni, nj)
a = pd.DataFrame([(i,j,k) for i,j,k in product(range(ni),
    range(nj),range(4))], columns=list('行列向'))
a['VDir'] = addbinvars(len(a))
a['VLen'] = addvars(len(a))
a[:2]

数理モデルを作り解く

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

数字があれば、方向別長さの和に等しく、かつその位置に矢印がないこと (1)
数字がなければ矢印は1方向のみ (2)
数字がなければ矢印の方向に長さを1足すこと (3)

python

drc = [(-1, 0, 0), (0, -1, 1), (0, 1, 2), (1, 0, 3)]
m = LpProblem()
for i,j in product(range(ni), range(nj)):
    b = a[(a.行==i)&(a.列==j)]
    if data[i][j].isdigit():
        m += lpSum(a[(a.行==i+y)&(a.列==j+x)&(a.向==k)].VLen
                   for y,x,k in drc) == int(data[i][j]) # (1)
        m += lpSum(b.VLen) == 0 # (1)
        continue
    m += lpSum(b.VDir) == 1 # (2)
    for y,x,k in drc:
        r = b[b.向==k].iloc[0]
        m += r.VLen <= mx * r.VDir # (3)
        m += r.VLen <= r.VDir + lpSum(
            a[(a.行==i+y)&(a.列==j+x)&(a.向==k)].VLen) # (3)
m.solve()

結果の表示

python

a['Val'] = a.VDir.apply(value)
print('\n'.join(''.join(' '+(data[i][j] if data[i][j].isdigit()
    else '↑←→↓'[int(value(lpDot([0,1,2,3],a[(a.行==i)&(a.列==j)].Val)))])
    for j in range(ni)) for i in range(nj)))
>>>
 4 → → 1 → ↑
 ↓ 4 → → 2 ↑
 ↓ ↓ 2 → ↓ 2
 1 ↓ ↓ 1 ↓ ↑
 ↓ 1 → ↓ 1 ↑
 ← ← 3 → ↓ 2

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

以上