dancing links

KnuthのTAOCP, 7巻の分冊が出回り始めた. その最初の方にexact cover problemを解くのにdancing linksが適してると書いてある.

dancing linksについてはKnuthが楽しんで書いた論文があり, 講義のビデオも存在する. exact cover proble (日本語では「敷き詰め問題」か) は条件をならべた行列から解の候補を選び, それにより使えなくなった行や列を外し, またback trackするときは, 外した行や列をもとにもどす.

この行列はスパースなので, 上下左右に双方向リンクで実装すると, うまくいくというのがdancing linksの話の味噌である.

私としては面白そうなアルゴリズムを知ったら, さっそくコーディングして例題を走らせ, 体験によってアルゴリズムを理解, 記憶することが多い.

dancing linksについてもさっそくプログラムを書いた. googleで探すとjavaなんかで書いたプログラムも見つかるが, 自分で書くのが楽しいのでschemeで書くことにした.

Knuthの論文の最初の簡単な例題は, 直ぐにうまくいったが, 当然dancing linksを使えばうまく解けると書いてある他の例は, 結構てこずった.

8×8-2×2の60区画にペントミノのピースを置く問題である. ピースXを左上の(3,3)に置くというのに挑戦た. ぜんぜん解が出てこないのである. 当然プログラムがおかしいかといろいろ見てみたが, 合っているとしか思えない.

実は候補の列を選ぶのに, ブランチ数の少ないものを選ぶと書いてあったが, そうしなくても解が出るようにも読めたので, 残っている列の最左端から選んだのが失敗であった. あるとき思いついて, ブランチ数最小の列を選んでみたら, たちまち最初の解が出た. 超簡単な例では, 最左端でも問題なく解が得られたが, ペントミノ程度になると, ブランチ数を考慮する必要があった.

dancing linksの双方向リンクによる削除挿入は, 野下浩平君とその学生の一松宏君が8クイーン問題を解くのに考えたといわれている. しかし縦と横はすべてにクイーンを置くので, exact cover problemであるが, 斜め方向は半分くらいしか埋めないので, この辺の扱いは別になる. Knuthの例の論文をよく読むと, こういうのはgeneralized exact cover problemというので, 列にはprimaryとsecondaryを用意する. primaryの列名は双方向リンクで接続するが, secondaryの列名は自分自身で循環するリンクにすると書いてあった. そういう風にプログラムをなおすと, なるほどうまく行った.

数独にも適しているといわれるdancing linksである. 数独ではいくつかの解が与えられているので, 解を探し始める前に, 与えられた解について列や行を削除する(coverする)必要がある. 解に相当する行を探す手間が必要で, この辺はプログラムでかなり工夫が必要であった.

最後に, 上下左右に双方向リンクにしないでも, 実装できるのではないかとプログラムをしてみた. ノードはlispの対で, carに下へのリンク, cdrに右へのリンクを置き, 循環するようにリストを実装すると, たしかにこれでもうまく出来ることがわかった.