ペントミノをExact cover問題として解く（その２）

前回の（その１）ではペントミノの解を総当りで求めるコードを作成しました。

今回は高速化するために使うExact cover問題にとそれを解くpackageのPyPIのDLXについて説明します。

（参考）Exact cover (Wikipedia)の考え方

4. Exact cover問題の考え方

Exact cover#Detailed exampleで示されている例を示します。

\begin{align}
&全体集合 X = \lbrace 1,2,3,4,5,6,7 \rbrace のとき\\
&その部分集合 \\
&A = \lbrace 1,4,7 \rbrace \\
&\color{red} {B = \lbrace 1,4 \rbrace} \\
&C = \lbrace 4,5,7 \rbrace \\
&\color{red} {D = \lbrace 3,5,6 \rbrace} \\
&E = \lbrace 2,3,6,7 \rbrace \\
&\color{red} {F = \lbrace 2,7 \rbrace} \\
&のうち共通要素を持たず和集合がXになる \\
&\color{red} {集合\lbrace B,D,F  \rbrace をExact \ cover}と呼びます\\
& \\
\end{align}

5 Exact cover問題を解くPyPIのDLXの説明

PyPIのDLXを使ってこの例題を解いてみます

PyPIのDLXpackageはKnuthのdancing linksアルゴリズム(Algorithm X)を実装したものす。

アルゴリズムに関しては以下のリンクに解説がありますが、ここではブラックボックスとして利用します。

Knuth's Algorithm XとDancing Linksの解説

こおDLX packageはちょっとクセがあるので使用法を詳細に説明します。

1. DLXのmoduleをインストールする
2. 列(column)のデータを作る(DLX)
3. 行(row)のデータを作る(appendRow)
4. 問題を解く(solve)
5. 答えを得る(getRowList)

5.1. DLXのmoduleをインストールする

!pip install dlx

5.2. 列(column)のデータを作る(DLX)

• DLXに渡す列データは[(列名0, 0), (列名1, 0),..]の形式（0はcover必須の列を表す）
• 次のappendRowで渡すデータは列名ではなくて列index(0スタート)なので、その関係を示す辞書(colidx)を作っておく
• 答えは「列名リスト」で得られるので「列名リストー＞集合名」の辞書の形式で部分集合ssetを定義

columns = [(x,0) for x in [1,2,3,4,5,6,7]]
print(f"columns = {columns}")
colidx = {c[0]: i for i, c in enumerate(columns)}    # column index
print(f"colidx = {colidx}")
sset = {(1, 4, 7): 'A', (1, 4): 'B', (4, 5, 7): 'C', (3, 5, 6): 'D', (2, 3, 6, 7): 'E', (2, 7): 'F'}
dlx = DLX(columns)
# columns = [(1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0)]
# colidx = {1: 0, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6}

5.3. 行(row)のデータを作る(appendRow)

各行のデータをappendRowを使って入れていきます。ここで要注意なのが指定するのは列名ではなくて列indexだと言うことです。したがってcolidxを使って変換してrowを作ります。

for sdata, sname  in sset.items():
  row = [colidx[i] for i in sdata]
  print(f"row = {row}")
  dlx.appendRow(row)   # add row
# row = [0, 3, 6]
# row = [0, 3]
# row = [3, 4, 6]
# row = [2, 4, 5]
# row = [1, 2, 5, 6]
# row = [1, 6]

5.4. 問題を解く(solve)

入力が終わったらsolveを呼ぶと答えが得られます。答えは複数ある場合もあるのでGeneratorの形で得られます。

5.5. 答えを得る(getRowList)

回答のsolutionはあまり意味のない数なのでgetRowListを使って列名のリスト（列indexではなくて）を取得します。これでも分かりますが、ssetで部分集合の名前に変換して最終解$ ['B', 'D', 'F']$が得られました。

for solution in dlx.solve():
  print(f"solution = {solution}")
  rowlist = [tuple(sorted(dlx.getRowList(i))) for i in solution]
  print(f"answer data = {rowlist}")
  print(f"answer subsets = {[sset[row] for row in rowlist]}")
# solution = [11, 17, 23]
# answer data = [(1, 4), (3, 5, 6), (2, 7)]
# answer subsets = ['B', 'D', 'F']

以上のようにDLX Packageは強力なツールなのですが、マニュアルがほとんどなく、コツが必要なので少し丁寧に説明しました。

次回（その３） ではいよいよDLX Packageを使ってペントミノを解いていきます

（開発環境：Google Colab）