数独

数独とは #

9×9のマスに1～9の数字を入れるペンシルパズルです。その際に、縦と横の各列と3×3で区切られたブロック内に同じ数字が複数入ってはいけないというルールの元に数字を埋めていきます。また、ヒントとして大体20個から30個程度のマスがすでに埋まっており、この前提のもとで数字を全てのますで埋めれば完成です。

ここでは数独をアニーリングマシンで解くための方法について解説します。

例題 #

次の問題を例題として扱います (引用元: 数独問題集-2018年3月1日-最高級-)。

一般的な数独の解法 #

まずは一般的な解法に従って数独の問題を解いてみます。基本的な解法の流れとしては次のようになります。

1. 与えられたヒントを元に一意に決まる数字を埋める。
2. 全て埋まったら、埋まっていないマスに入る可能性のある数字を列挙する
3. 入る可能性のある数字を仮置きして他の場所を埋める
4. 最後まで埋まる前に矛盾が生じたら仮置きを変えてやり直す
5. 全てのマスが埋まるまで4を繰り返す
6. 完成

簡単な問題は手順1だけで最後まで埋めることができますが、難しい問題では2以降の試行錯誤が必要になります。この単純なアルゴリズムで数独を機械的に解く場合、この試行錯誤は深さ優先探索に相当し、問題によっては答えを得るまでにかなりの時間がかかることがあります。

アニーリングマシンで数独を解く #

アニーリングマシンは組合せ最適化問題を解くことに特化したマシンです。一般的な解法の2以降の手順について、「入る数字の組合せで正しい解が決まる」という部分を組合せ最適化問題と解釈し、アニーリングマシンで実際に解いてみます。

コスト関数の作成 #

アニーリングマシンで問題を解くためには、コスト関数を定義する必要があります。まずはどのようにしてコスト関数を構築するのかを説明します。

例題を手順1に従い一意に決まる場所を埋めると以下のようになります。

この状態が今回の問題の出発点となります。埋まってない箇所は複数の数字が入る可能性がありますが、

1. ひとつのマスの中にはひとつの数字しか入れることができない
2. 縦と横の列と3×3ブロックの中には同じ数字が入ってはいけない

というルールに基づいて決まります。この制約をコスト関数として解釈し、制約を満たす「正しい組合せ」の時のみコスト関数が最小となるように設計することが出来ればアニーリングマシンで実行することが可能になります。

コスト関数を構築するにはこれを表わす変数と式によって組み立てる必要があります。変数として、値が 0 か 1 しか取らない QUBO 変数を用い、あるマスにある数字が入る場合に 1 を、入らない場合に 0 を取ることにします。

マス中の制約 #

例えば0行1列目のマスに入る可能性がある数字は7と8です。どちらかの数字しか入らないようにするには、両方の数字が入った場合とどちらの数字も入らなかった場合にコストが上がるように式を組み立てます。以下では説明のために、7が入るかを表わす変数を \(a\) 、8が入るかを表わす変数を \(b\) とします。

結論としては、下記のようなコスト関数を導入すればこの制約を表現できます。

確かめてみると、 \((a, b) = (1,0),(0,1)\) の場合に値 \(-1/2\) 、 \((a,b)=(0,0),(1,1)\) の場合に値 \(0\) をとることがわかります。変数どちらかが 1 のときだけ最小値をとるようになっています。

ひとつのマスの中に 3 変数が入る場合、上の式を拡張することで同様に組み立てることができます。

この時もひとつの変数だけ 1 のときに最小値 \(-1/2\) となります。

このようにして全てのマスについて、制約条件を表わす式を組み立て、全て足し合わせることで「ひとつのマスの中にはひとつの数字しか入れることができない」に対応したコスト関数が構築されます。

マスとマスの間の制約 #

次に行と列とブロックの中に同じ数が入ってはいけない制約についてコスト関数を組み立てます。

例として左上のブロックについてみてみます。以下の図では各マスに入る可能性の数字のうち、同じ数字同士を矢印で繋いでみました。

ブロック内での制約は、繋がっている数字を表わす変数が同時に 1 にならないようにすることで表わされます。先ほどと同じように、それぞれのペアの変数を \(a\) , \(b\) として、

をコスト関数とすれば良いです。確認すると、 \((a,b) = (1,1)\) のとき値 \(1\) をとり、それ以外のときは最小値 \(0\) となります¹。

以上を全てのブロック・行・列の中に含まれるペアについて足し合わせることで、マスとマスの間の制約のコスト関数が構築されます。

以上の二種類の制約条件を表わすコスト関数を足し合わせることで、アニーリングマシンに入力する最終的なコスト関数が完成します。

結果 #

D-Wave の量子アニーリングマシン D-Wave 2000Q を用いて解くと、下記の解が得られました。

行・列・ブロックの中に同じ数字が2回以上現れていないため、正しい解が得られていることがわかります。このように、適切にコスト関数を設定することにより、条件を満たすような最適な答えをアニーリングマシンから得られます。

次に、もっと難しい数独の問題をアニーリングマシンで解いてみます。数独の実装方法さえ確立してしまえば、同じ方法を使ってどのような数独の問題でも実行することが出来るはずです。

世界一難しい数独 #

フィンランド人の数学者である Arto Inkala 氏が「世界一難しい数独」として2012年に発表した問題を、アニーリングマシンを使って解いてみます。

この問題を最適化問題に帰着させた後、コスト関数を作るために必要な変数を見積もると 254 個となりました。そのため解空間が非常に広く、工夫もなしに探索すると解を見つけ出すのにかなりの時間を要する可能性があります。

解いた結果は以下のようになりました。

これは数独の解の条件を満たしており、また Arto Inkala氏が発表した解と一致しています。

スパコンで力任せに数独の難しい問題を作るったつもりが簡単な問題だった件 #

2013年にスパコンを使って制作された問題を解いてみます。

これは、製作者の難易度の定義によると、Arto Inkala氏が制作した問題より40倍以上難しいとされているため、通常の探索では非常に時間がかかる可能性があります。実際、この問題に対して単純に深さ優先探索を行うと数万回程度再帰を必要とするため、人間が解くのにはかなりの時間を要すると思われます。

しかしながら、こちらもアニーリングマシンを使うことにより解を求めることが出来ました。

この問題は解が公表されていないために確認することはできませんが、数独の条件を満たしているため適切な解であると思われます。

何も埋まっていない数独の問題を解く #

一箇所もヒントが与えられていない数独の問題をアニーリングマシンで解くとどのようになるのでしょうか。これは 729個もの変数を必要とし、また、9072個もの変数間の結合を必要とします。そのため、ある意味アニーリングマシンにとっては、上の問題よりも解くことが難しい、規模の大きい問題である可能性もあります。

実際にアニーリングマシンで解くことには成功しましたが、問題を解くたびに、異なる数独の解の条件を満たす解が返ってきます。数独は、ユニバーシティ・カレッジ・ダブリンの数学者 Gary McGuire氏により、ヒントが16個以下だと一意に解くことができないということが示されています²。つまりアニーリングマシンにおいては、ヒントが16個以下のときはコスト関数を最小とする解が一意に定まらないということを意味します。

一般的なアルゴリズムでは解が多数ある方が問題は解きやすそうにも思います。しかしアニーリングマシンにおいてもそうでしょうか、変数や結合などの問題の規模が大きくなる方が最適解は得られにくくなるようにも思います。この関係性について現時点ではよくわかっていませんが、将来の調査テーマとして興味深いです。

最後に #

数独はNP完全として効率的に解くことが出来ない問題として知られています。通常のコンピュータで解く場合には、アルゴリズムの最適化や様々なテクニックの実装により計算に工夫を施す必要があります。しかしながら、アニーリングマシンで解く場合には、適切にコスト関数を用意すれば、比較的単純に解かせることが可能です。問題の詳細に触れず、汎用的に実行できることがアニーリングマシンの重要な特徴のひとつです。