M.Hiroi's Home Page

Algorithms with Python

Dancing Links

[ PrevPage | Python | NextPage ]

はじめに

Algorithm X と Dancing Links は、クヌース先生が開発した Exact Cover Problem という問題を解くためのアルゴリズムとデータ構造です。前回に引き続き簡単な「敷き詰め問題」を例題にして、今回は Dancing Links について説明します。

●Dancing Links とは？

クヌース先生の Dancing Links は、行列の 1 の要素を縦方向と横方向の双方向リストでつないだデータ構造です。Dancing Links の図を再掲します。

H は行列全体のヘッダーで、1, 2, 3, 4, 5 が列を表すヘッダーです。列のヘッダーから縦のリンクをたどれば、要素を含む部分集合を簡単に求めることができます。また、横のリンクをたどれば、その部分集合の要素も簡単に求めることができます。

双方向リストの場合、リンクから節 (node) を削除したり、それを元に戻すことは節のデータを書き換えることで簡単にできます。列を取り除く場合、列ヘッダーをつないでいる横のリンクから、該当する列のヘッダーを削除すればいいわけです。部分集合を削除する場合は、節の横のリンクをたどり、縦のリンクから節を削除することで実現できます。

節 (node) の構造を図に示すと次のようになります。

prev と next で横方向の節を連結し、up と down で縦の節を連結します。節の基本的な操作は双方向リストと同じです。双方向リストの説明は、拙作のページ 連結リストとキュー をお読みください。

●Dancing Links の操作方法

Dancing Links から列と行を取り除く操作は簡単です。選択した部分集合の節を node としましょう。node の横のリンクをたどると、削除する列を求めることができます。node の縦のリンクをたどると、削除する部分集合を求めることができます。

Dancing Links の場合、列をひとつ削除したら、その列に属する部分集合を削除します。このとき、node につながっている縦のリンクは残しておいて、それ以外の節を縦のリンクから外すところがポイントです。列に属する部分集合を削除したあと、node の横のリンクをたどり、次の列を削除します。

簡単な例を示しましょう。次の図を見てください。

最初に、列 4 にある節 C4 を選択します。次に、列ヘッダー 4 をヘッダーのリンクから外します。このとき、節 C4 は縦のリンクから削除しません。その次に、C4 の縦のリンクをたどりますが、ヘッダー以外の節はないので、C4 の横のリンクをたどります。

次に、節 C3 の列を削除します。列ヘッダー 3 を削除し、C3 の縦のリンクをたどります。すると、節 B3 が見つかるので、B3 の横のリンクをたどって、節を縦のリンクから外します。このとき、B3 は縦のリンクから削除しません。B3 の横のリンクをたどると、節 B2 が見つかります。B2 を列 2 から削除します。

横のリンクから外した節を赤色で、縦のリンクから外した節を黄色で示すと、次のようになります。

次は列 1 の節 A1 を選びます。最初に、列ヘッダー 1 を削除して、A1 の縦のリンクをたどります。すると、節 D1 が見つかるので、D1 の横のリンクをたどって、節 D5 を縦のリンクから外します。列 1 にリンクされている節はこれだけです。

次に、A1 の横のリンクをたどると、節 A2 が見つかります。列ヘッダー 2 を削除して、A2 の縦のリンクをたどります。B2 は削除されているので、節 F2 が見つかります。F2 の横にリンクされている節はないので、節の削除は行いません。

あとは、同様に列 5 の節 E5 を選ぶと行列は空になります。ここで、解をひとつ見つけることができました。

Dancing Links を復元する場合も同様の操作で行うことができます。ただし、節をリンクから外したときと逆の順番で節をリンクに戻すことに注意してください。節を横のリンクから外すとき、next の方向へ節をたどったならば、復元するときは prev の方向へたどります。縦のリンクから外すとき、down の方向へたどったならば、復元するときは up の方向へたどります。たとえば、列ヘッダー 3, 4 を削除したとき、4, 3 の順番で削除したので、戻すときは 3, 4 の順番で行います。

文章で説明すると複雑な処理のように思えますが、実際にプログラムを作ってみると簡単なので心配しないでください。

●データ構造の定義

それではプログラムを作りましょう。最初にデータ構造を定義します。 

リスト : データ構造の定義

# 節の定義
class Dnode:
    def __init__(self, n):
        self.up   = self   # 列のリンク
        self.down = self
        self.next = self   # 行のリンク
        self.prev = self
        self.num  = n      # 行 (列) の番号
        self.head = self   # 列ヘッダー
        self.size = 0      # 列の長さ

節はクラスで定義します。名前は Dnode としました。up, down, prev, next は縦と横のリンクを表します。num は列または行の番号を格納し、head は列ヘッダーを格納します。節が列ヘッダーの場合は自分自身を格納します。size は列の長さを表します。列ヘッダー以外の節は 0 にセットします。

次は Dancing Links のヘッダーを定義します。 

リスト : ヘッダーの定義

# ヘッダー
Header = None

# ヘッダーの初期化
def initHeader():
    global Header
    Header = Dnode(-1)

Dancing Links は大域変数 Header に格納します。初期化は関数 initHeader() で行います。 Dnode(-1) で空のヘッダーを生成して Header にセットするだけです。

●Dancing Links の生成

次は Dancing Links を生成する処理を作りましょう。 

リスト : Dancing Links の生成

def makeDancingLinks(xss):
    initHeader()
    for line, xs in enumerate(xss):
        hNode = Dnode(line)
        insertCol(xs[0], hNode)
        for i in range(1, len(xs)):
            node = Dnode(line)
            insertCol(xs[i], node)
            insertLine(hNode, node)

Dancing Links は関数 makeDancingLinks() で生成します。引数 xss は部分集合を格納したリストです。initHeader でヘッダーを初期化して、for ループで xss から部分集合を取り出して Dancing Links へ追加していきます。変数 line は行番号を、変数 xs は xss の要素 (部分集合) を表します。

最初に xs の先頭要素を表す節を Dnode(line) で生成して変数 hNode にセットします。横のリンクはヘッダーを用意しないで、hNode を行のヘッダーとして使います。それから、hNode を関数 insertCol() に渡して列の末尾に挿入します。insertCol() の第 1 引数が列番号、第 2 引数が挿入する節です。あとは for ループで残りの要素を取り出して節 node を生成し、insertCol() で列の末尾に挿入したあと、insertLine() で行の末尾に挿入します。

次は行の末尾に節を挿入する関数 insertLine() を作ります。 

リスト : 行の末尾に節を追加

def insertLine(header, node):
    node.prev = header.prev
    node.next = header
    header.prev.next = node
    header.prev = node

引数 header が行のヘッダー、node が挿入する節です。header.prev と header の間に node を挿入するので、node.prev は header.prev に、node.next は header に書き換えます。それから、header.prev の next を node に、header の prev を node に書き換えます。この操作は双方向リストのデータ挿入とまったく同じです。

次は列の末尾に節を挿入する関数 insertCol() を作ります。 

リスト : 列の末尾に節を追加

def insertCol(col, node):
    header = searchHeader(col)
    header.size += 1
    node.head = header
    node.down = header
    node.up   = header.up
    header.up.down = node
    header.up = node

引数 col が列の番号、node が末尾に挿入する節です。最初に、関数 searchHeader() で col 番目の列ヘッダーを求めて変数 header にセットします。node は header.up と header の間に挿入します。挿入の方法は insertLine() と同じです。このとき、header の size を +1 して、node の head を列ヘッダーに書き換えます。

次は n 番目の列を探す関数 serachHeader() を作ります。 

リスト : n 番目の列ヘッダーを探す

def searchHeader(n):
    global Header
    node = Header.next
    while node is not Header:
        if node.num == n: return node
        node = node.next
    # 新しい列ヘッダーを作成する
    newNode = Dnode(n)
    insertLine(Header, newNode)
    return newNode

Header からリンク next を順番にたどり、num の値が n のヘッダーを探します。見つからない場合は新しい列ヘッダーを Header の末尾に追加します。列ヘッダーは Header の横にリンクされているので、末尾に挿入する処理は insertLine() で行うことができます。

●行と列の削除

次は Dancing Links から行と列を削除する処理を作ります。 

リスト : 行と列の削除

def removeMatrix(hNode):
    node = hNode
    while True:
        # 列ヘッダーを外す
        header = node.head
        header.prev.next = header.next
        header.next.prev = header.prev
        # 縦のリンクをたどる
        cNode = node.down
        while cNode is not node:
            # 列ヘッダーをスキップ
            if cNode is not cNode.head:
                # 横のリンクをたどる
                lNode = cNode.next
                while lNode is not cNode:
                    # 縦のリンクから外す
                    lNode.up.down = lNode.down
                    lNode.down.up = lNode.up
                    lNode.head.size -= 1
                    lNode = lNode.next
            cNode = cNode.down
        node = node.next
        if node is hNode: break

removeMatrix() の引数 hNode が選択した部分集合の要素 (節) です。最初の while ループで hNode の横のリンクを next 方向へたどります。ループの中で、最初に列ヘッダー header を求め、それを横のリンクから外します。この操作は双方向リストの操作とまったく同じです。

次の while ループで、node の縦のリンクを down 方向へたどります。このとき、列ヘッダーをスキップすることと、節 node は縦のリンクから削除しないことに注意してください。node 以外の節を見つけたら、次の while ループで横のリンクを next 方向へたどります。この中で、節 lNode を縦のリンクから外します。このとき、列ヘッダーの size を -1 することと、節 cNode は縦のリンクから外さないことに注意してください。

●行と列の復元

次は、行と列を復元する関数 restoreMatrix() を作ります。 

リスト : 行と列の復元

def restoreMatrix(hNode):
    node = hNode.prev
    while True:
        # 列ヘッダーを元に戻す
        header = node.head
        header.prev.next = header
        header.next.prev = header
        # 縦のリンクをたどる
        cNode = node.up
        while cNode is not node:
            # 列ヘッダーをスキップ
            if cNode is not cNode.head:
                # 横のリンクをたどる
                lNode = cNode.prev
                while lNode is not cNode:
                    # 縦のリンクに追加
                    lNode.up.down = lNode
                    lNode.down.up = lNode
                    lNode.head.size += 1
                    lNode = lNode.prev
            cNode = cNode.up
        if node is hNode: break
        node = node.prev

引数 hNode が選択した部分集合の要素 (節) です。removeMatrix() は hNode から始めて横のリンクを next 方向へたどりました。restoreMatrix() は hNode の横のリンクを prev 方向へたどり、hNode を一番最後に復元します。

while ループの中で、最初に列ヘッダーを横のリンクに戻します。この処理も双方向リストとまったく同じです。次の while ループで node の縦のリンクを up 方向へたどります。そして、節 cNode の横のリンクを prev 方向へたどります。たどる方向は removeMatrix() の逆方向であることに注意してください。そして、節 lNode を縦のリンクに戻します。このとき、列ヘッダーの size を +1 することをお忘れなく。

●Dancing Links による Algorithm X の実装

最後に、Dancing Links を使用した Algorithm X のプログラムを作ります。 

リスト : Algorithm X + Dancing Links

# 最小の列を選択する
def selectMinCol():
    global Header
    minNode = Header.next
    node = minNode.next
    while node is not Header:
        if node.size == 0: return node
        if node.size < minNode.size:
            minNode = node
        node = node.next
    return minNode

# 空行列か
def isEmpty():
    global Header
    return Header is Header.next

def algoDLX(f, xss):
    def algoSub(a):
        if isEmpty():
            f(a)
        else:
            # 列の選択
            cNode = selectMinCol()
            # 行の選択
            lNode = cNode.down
            while lNode is not cNode:
                removeMatrix(lNode)
                a.append(xss[lNode.num])
                algoSub(a)
                a.pop()
                restoreMatrix(lNode)
                lNode = lNode.down
    #
    makeDancingLinks(xss)
    algoSub([])

関数 selectMinCol() は選択肢が最小の列を線形探索で求めます。関数 isEmpty() は列ヘッダーがなくなったときに True を返します。関数 algoDLX() は makeDancingLinks で Dancing Links を生成し、局所関数 algoSub() を呼び出して解を探索します。

algoSub() は簡単です。行列が空になったか isEmpty() でチェックします。空行列の場合、関数 f に累積変数 a を渡して呼び出します。そうでなければ、selectMinCol() で最小の列を選択して変数 cNode にセットします。

次に for ループで cNode の縦のリンクをたどり、行 (部分集合) を選んで変数 lNode にセットします。そして、removeMatrix() で lNode が属している列と行を削除し、algoSub() を再帰呼び出しします。戻ってきたら、resotreMatrix() で行と列を元に戻します。

●実行結果

それでは、実行してみましょう。前回と同様に L トロミノの敷き詰め問題を解いてみました。 

            表 : 実行結果

 盤面 | A  |    総数 | AlgoX  |  DLX
------+----+---------+--------+-------
7 * 7 |  0 |    1440 |  0.158 | 0.016
------+----+---------+--------+-------
8 * 8 |  0 |   30355 |  0.821 | 0.210
------+----+---------+--------+-------
9 * 9 | -- | 1193600 | 35.413 | 8.273

 A : 取り除く正方形の位置
 
実行環境 : PyPy 7.3.1, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

AlgoX は前回作成した連想リストで実装した Algorithm X の結果で、DLX が今回作成した Dancing Links を用いた Algorithm X の結果です。どの盤面も DLX のほうが速くなりました。

ちなみに、Python 3.8.10 で試してみると、9 * 9 盤で AlgoX が約 128 秒、DLX が約 113 秒かかります。DLX は確かに効果があるのですが、Python にはちょっと荷が重い処理だったようです。ネイティブコードにコンパイルするプログラミング言語を使えばもっと速くなるでしょう。興味のある方は試してみてください。

●参考文献, URL

  1. 数理パズル入門, L-トロミノの敷き詰め
  2. Exact cover - Wikipedia (en)
  3. Donald Knuth, "Dancing Links (PDF)"
  4. Knuth's Algorithm X - Wikipedia (en)
  5. Dancing Links - Wikipedia (en)

●プログラムリスト

#
# tromino.py : トロミノの敷き詰め (Algorithm X + Dancing Links)
#
#              Copyright (C) 2014-2022 Makoto Hiroi
#
import time

# L トロミノの生成
def makeLtromino(w, h):
    tbl = []
    for x in range(0, w - 1):
        for y in range(0, h - 1):
            z = y * w + x
            tbl.append([z, z+1, z+w       ])
            tbl.append([z, z+1,      z+w+1])
            tbl.append([z,      z+w, z+w+1])
            tbl.append([   z+1, z+w, z+w+1])
    return tbl

# ヘッダー
Header = None

# 節の定義
class Dnode:
    def __init__(self, n):
        self.up   = self   # 列のリンク
        self.down = self
        self.next = self   # 行のリンク
        self.prev = self
        self.num  = n      # 行 (列) の番号
        self.head = self   # 列ヘッダー
        self.size = 0      # 列の長さ

# ヘッダーの初期化
def initHeader():
    global Header
    Header = Dnode(-1)

# 行の最後尾に挿入する
def insertLine(header, node):
    node.prev = header.prev
    node.next = header
    header.prev.next = node
    header.prev = node

# 列ヘッダーを求める
def searchHeader(n):
    global Header
    node = Header.next
    while node is not Header:
        if node.num == n: return node
        node = node.next
    # 新しい列ヘッダーを作成する
    newNode = Dnode(n)
    insertLine(Header, newNode)
    return newNode

# 列の最後尾に挿入する
def insertCol(col, node):
    header = searchHeader(col)
    header.size += 1
    node.head = header
    node.down = header
    node.up   = header.up
    header.up.down = node
    header.up = node

# Dancing Links の作成
def makeDancingLinks(xss):
    initHeader()
    for line, xs in enumerate(xss):
        hNode = Dnode(line)
        insertCol(xs[0], hNode)
        for i in range(1, len(xs)):
            node = Dnode(line)
            insertCol(xs[i], node)
            insertLine(hNode, node)

# 最小の列を選択する
def selectMinCol():
    global Header
    minNode = Header.next
    node = minNode.next
    while node is not Header:
        if node.size == 0: return node
        if node.size < minNode.size:
            minNode = node
        node = node.next
    return minNode

# 空行列か
def isEmpty():
    global Header
    return Header is Header.next

# 行と列の削除
def removeMatrix(hNode):
    node = hNode
    while True:
        # 列ヘッダーを外す
        header = node.head
        header.prev.next = header.next
        header.next.prev = header.prev
        # 縦のリンクをたどる
        cNode = node.down
        while cNode is not node:
            # 列ヘッダーをスキップ
            if cNode is not cNode.head:
                # 横のリンクをたどる
                lNode = cNode.next
                while lNode is not cNode:
                    # 縦のリンクから外す
                    lNode.up.down = lNode.down
                    lNode.down.up = lNode.up
                    lNode.head.size -= 1
                    lNode = lNode.next
            cNode = cNode.down
        node = node.next
        if node is hNode: break

# 行と列の復元
def restoreMatrix(hNode):
    node = hNode.prev
    while True:
        # 列ヘッダーを元に戻す
        header = node.head
        header.prev.next = header
        header.next.prev = header
        # 縦のリンクをたどる
        cNode = node.up
        while cNode is not node:
            # 列ヘッダーをスキップ
            if cNode is not cNode.head:
                # 横のリンクをたどる
                lNode = cNode.prev
                while lNode is not cNode:
                    # 縦のリンクに追加
                    lNode.up.down = lNode
                    lNode.down.up = lNode
                    lNode.head.size += 1
                    lNode = lNode.prev
            cNode = cNode.up
        if node is hNode: break
        node = node.prev

# Algorithm X + Dancing Links
def algoDLX(f, xss):
    def algoSub(a):
        if isEmpty():
            f(a)
        else:
            # 列の選択
            cNode = selectMinCol()
            # 行の選択
            lNode = cNode.down
            while lNode is not cNode:
                removeMatrix(lNode)
                a.append(xss[lNode.num])
                algoSub(a)
                a.pop()
                restoreMatrix(lNode)
                lNode = lNode.down
    makeDancingLinks(xss)
    algoSub([])

# L トロミノの敷き詰め
# n * n - 1
def solverLtromino1(n, m):
    c = [0]
    def counter(xs):
        if c[0] == 0: print(xs)
        c[0] += 1
    #
    ls = [xs for xs in makeLtromino(n, n) if m not in xs]
    algoDLX(counter, ls)
    return c[0]

# n * n
def solverLtromino(n):
    c = [0]
    def counter(xs):
        if c[0] == 0: print(xs)
        c[0] += 1
    #
    ls = makeLtromino(n, n)
    algoDLX(counter, ls)
    return c[0]
初版 2014 年 1 月 19 日
改訂 2022 年 9 月 17 日
Copyright (C) 2014-2022 Makoto Hiroi
All rights reserved.
[ PrevPage | Python | NextPage ]