Exact Cover Problemとそれを応用した数独解読アルゴリズム

Exact Cover Problemを知ったきっかけ

先日、演習の一環で数独を解読を行うアルゴリズムJavaで書くという演習がありました。どうせなら早く解けるようにしたいということで何かいいアルゴリズムはないかと調べました。そしたらこのような記事を見つけました。 d.hatena.ne.jpこの記事で紹介されている問題とアルゴリズムを使うと数独を解くプログラムができるらしいです。 Exact Cover Problemとそれを解くKnuth's Algorithm Xについては引用元の記事をご覧ください。

Exact Cover Problemを数独に応用する

数独問題=Exact Cover Problem

人間が数独を解くときは「ここには何が入りそうだ」とかを考えて解候補をマスの端に書いたりして考えます。今回紹介するExact Cover Problemもそれに似た感じです。

数独をExact Cover Problemとしてみる

数独として成り立つには次のような条件があります。

  • 各行と各列が交差する部分つまり各セルには必ず正確な数字が入っている必要がある。...行と列の関係
  • 各行には正確な数字が重複しないようにはいっている必要がある。...行と数字の関係
  • 各列には正確な数字が重複しないように入っている必要がある。...列と数字の関係
  • 各ボックスには正確な数字が重複しないように入っている必要がある。...ボックスと数字の関係

上記の4つの条件をすべての行、列、ボックスにおいてすべて満たすと数独的に正しいことになります。Exact Cover Problemとして考えるには人間がマスの端に可能性のある数字を書き込むようにこの各条件と考え得るすべての場合と照らし合わせて考えます。考え得るすべての場合というのは「1行1列に1が入る場合」、「1行1列に2が入る場合」、...「9行9列に9が入る場合」までを考えます。そしてそれらは各条件を持った集合です。例えば「1行1列に1が入る場合」というのは{1行1列に数字がある、1行目に1がある、1列目に1がある、一つ目のボックスに1がある}という4つの元を持った集合です。そしてこれらの元は他の場合と重複して持っていてはいけません。かつすべての条件を網羅していてなくてはいけません。つまり数独はExact Cover Problemなのです。

Knuth's Algorithm Xに数独を適用する

数独がExact Cover Problemであることは前節でわかっていただけたでしょうか。ここからはExact Cove Problemとして数独を見たときにそれをコンピュータにどう解かせるかを考えていきます。引用させていただいたJAPL JさんのブログによるとKnuth's Algorithm Xのアルゴリズムでは各元とそれを持った集合の関係行列を用意していました。これを前節で説明したものに適用する前に表現を定義しておきます。まずすべての考え得る場合からです。「m行n列に数字pがはいる場合」というのはRmCn#pと記述することにします。例えば「3行6列に数字8が入る場合」というのはR3C6#8となります。次に条件について考えます。行と列の関係についてm行n列に数字が入っているという条件はRmCnと記述することにします。行と数字の関係についてm行目に数字pが入るという条件はRm#pと記述します。列と数字の関係についてn列目に数字pが入るという条件はCn#pと記述します。ボックスと数字の関係についてx番目のボックスに数字pがはいるという条件はBx#pと記述します。定義をまとめると以下のようになります。

  •  m行n列に数字pが入る場合:= RmCn\verb|#|p
  •  m行n列に数字が入る条件:= RmCn
  •  m行に数字pが入る条件:= Rm\verb|#|p
  •  n列に数字pが入る条件:= Cn\verb|#|p
  •  x番目のボックスに数字pが入る条件:= Bx\verb|#|p

これを基に数独の関係行列を作成すると以下のようになります。( 729 \times 324の行列なので間を省略)

R1C1 R1C2 \cdots R9C9 R1#1 R1#2 \cdots R9#9 C1#1 C1#2 \cdots C9#9 B1#1 B1#2 \cdots B9#9
R1C1#1 1 0 \cdots 0 1 0 \cdots 0 1 0 \cdots 0 1 0 \cdots 0
R1C1#2 1 0 \cdots 0 0 1 \cdots 0 0 1 \cdots 0 0 1 \cdots 0
\vdots
R1C1#9 1 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0
R1C2#1 0 1 \cdots 0 1 0 \cdots 0 0 0 \cdots 0 1 0 \cdots 0
R1C2#2 0 1 \cdots 0 0 1 \cdots 0 0 0 \cdots 0 0 1 \cdots 0
\vdots
R1C9#9 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 1 0 0 \cdots 0
R2C1#1 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0 1 0 \cdots 0
R2C1#2 0 0 \cdots 0 0 0 \cdots 0 0 0 \cdots 0 0 1 \cdots 0
\vdots
R9C9#9 0 0 \cdots 1 0 0 \cdots 1 0 0 \cdots 1 0 0 \cdots 1

しかし、この関係行列は数独問題が全くの空白の場合です。数独の問題を解く時は大抵、所々に初期値が入っているのものです。例えば3行2列目に数字9が入っていることがわかっていたとしましょう。そうすると関係行列のR3C2、R3#9、C2#9、B1#9の列はすべて1になります。なぜならどの場合を考えたとしてもそれらの列の条件を満たしているのは明らかだからです。そしてR3C2#1~R3C2#8の8行はすべて消えます。なぜならこれらの行の場合はあり得ないからです。この行列を解いて残った解候補が答えとなります。

プログラムを書く

数独アルゴリズムで解くビジョンが見えてきたと思います。次にこれをプログラムに解かせるにはどうすれば効率がよいかを考えます。

今回の演習はJavaの演習なのでJavaで実装しければなりません。 考えた末全然実装方法が思いつかなかったのでネットの力を頼ることにしました。そしたらGitHubにExact Cover Problemを実装したソースコードがありました。それが以下になります。

github.com

rafalioさんという方が数独Knuth's Algorithm Xで解くプログラムをJavaで実装されていました。最初プログラムを見た時はちんぷんかんぷんでしたが時間をかけながら一つずつ理解していきました。rafalioさんが書かれたプログラムにできるだけ細かくコメントを記述したものをGitHubに上げました。以下になります。

※ただし、演習で使う用に改造したので元のソースコードとは異なる部分があります。

github.com

メソッドなどの詳しい動作説明

自分が解釈や理解に苦しんだクラスやメソッドを選んで説明させていただきます。

Dancing Links

引用元のブログでも紹介している通りDancing Linksという概念を用いてKnuth's Algorithm Xを解きます。DancingLinksについて概要だけ述べます。

  • 上下左右に双方向に繋がる自己参照型リスト
  • 今回の場合行列の1になる部分だけリンクする疎行列のスタイル
  • 各列の一番上にはカラムノードという列を表すノードがある
    hookRigntメソッドとhookDownメソッド
    ノード同士の連結にはノードを引数に取るhookRightメソッドとhookDownメソッドで実装されています。それぞれ引数にとったノードを右または下にリンクさせる関数です。この関数だけで双方向のリンクを実現するので左または上にリンクさせる関数は不要です。hookRight関数を例にリンクの様子を説明すると以下のようになります。 f:id:muscle_keisuke:20150919060738j:plain 図はn1が端のノードではないことを前提に作っています。もしn1が端のノードの場合はn1.Rは循環して最初のノードとなります。hookDownメソッドも同様です。 このメソッドを繰り返すことでDancingLinksを形成します。
    DancingNodeクラスとColumnNodeクラス
    Knuth's Algorithm Xには「列の中で一番1が少ない列を選択する」という動作があります。この時使うのがColumnNodeです。ColumnNodeはフィールドにString型を持ち自分が何列目かをそこに格納します。各DancingNodeはフィールドにColumnNodeを持ち、自分自身が何列目かがわかることができます。
    unLinkUDメソッド,unLinkLRメソッド
    次に削除の手順を示します。DancingNodeのメソッドにunLinkLR,unLinkUDの2つのメソッドがあります。これらを使って削除を行います。f:id:muscle_keisuke:20150919065412j:plainこれらのメソッドによって違うノードからの参照ができなくなります。
    coverメソッド
    前節で説明したunLinkUD,unLinkLRメソッドを使い列ごとの削除を行います。正確にいうと削除ではありません。正確に言うとノードを覆い(cover)、見えなくします。そうすることによって列を削除したと見なして処理を続けます。なぜいっそのこと削除しないのかという話になります。それは後で列の復元をする必要があるからです。Knuth's Algorithm Xでは列を選択した後、「その列に1が含まれる行を1つだけ選択するという動作」があります。その行の選択の仕方によって解が変わる可能性があります。最悪の場合解が出ないことがあります。しかし、それを事前に判断することができません。rafalioさんのソースコードではすべての行をfor文で網羅しています。そして再帰関数によって最後まで処理を試みます。ここで解なしが発生した場合再帰処理から復帰しなければなりません。その際に列を完全に削除してしまうと復元ができないのでcoverするにとどまるというわけです。
    reLinkUDメソッド,reLinkLRメソッド
    unLinkUD,unLinkLRメソッドによって参照不能になったメソッドを再び双方向に戻します。UDのほうが上下に双方向,LRが左右に双方向を復元させます。
    uncoverメソッド
    coverメソッドによって覆った列を復元するメソッドです。他のノードからは参照できませんが自分自身のノードからは参照できるのでそこからreLinkUD,reLinkLRによって双方向に戻します。coverメソッドを発動した時点でガベージコレクションに削除されない理由を次の節で説明します。
    knuthsAlgoritmXメソッド

    プログラムの心臓部です。内部でselectColumnNodeHeuristicメソッドという1が最も少ないColumnNodeを返すメソッドを呼んでいます。そのメソッドによって返されたColumnNode及びそこから参照できるすべてのDancingNodeが属するColumnNodeをcoverメソッドで参照できなくします。その際にガベージコレクションによって回収されないようにanswerというコレクションに対象のDancingNodeを追加します。内部でknuthsAlgoritmXメソッド再帰的に呼び出し、行列が0になるかもしくはリンクするDancingLinkがなくなるまで行います。行列が0になった場合は成功なのでanswerをhandlerクラスのhandleSolutionメソッドという解を決定づけるメソッドの引数に渡します。リンクするDancingLinkがなくなるつまり1を全く含まない列が出てきた場合は解なしなのでそのままメソッドを終了していきます。関数を終了するとその後に復元処理をする必要があります。次の行について調べる必要があるからです。ガベージコレクションに回収されないようにanswerに格納していたDancingNodeを取り出します。answerからはDancingNodeを削除します。取り出したDancingNode及びそこからたどれるすべてのDancingNodeについてuncoverを行い列を復元させます。そのレベルにおいて全ての行の探索が終われば列を復元させて同じ処理を行います。このような具合に解を見つけていきます。以下にknuthsAlgorithmXの簡単なフローチャートを載せておきます。

f:id:muscle_keisuke:20151104090643p:plain