8クイーン問題をイジングマシンで解いてみた

　『月刊インターフェース』という技術系の雑誌がCQ出版社から出版されている。この雑誌は、プログラミングやマイコン工作のような実用的なトピックを、初心者にもとっつきやすい形で紹介している。この雑誌の先月号の特集が量子コンピューターであった。「量子コンピューターの原理はこれだ！」とか、「量子コンピューターが実現したらビジネスでこんないいことがある！」とか、一般人からしたら雲をつかむような話だけでは終わらず、最近の流行である、クラウド経由で実際に量子コンピューターのプログラミングを行う例を紹介している。量子コンピューターをこんな風に触れる未来が訪れるなんて、僕が初めて量子コンピューターを知った15年前には想像できなかった。感無量である。

　特集に書かれていたサンプルプログラムを見てみると、思った以上に簡単であった。これなら俺でも何かできそうだ、と思ったので、いわゆる『８クイーン問題』を量子コンピューターで解くプログラムを自分で組んでみた。この記事ではその解説をしてみたい。
　なお、正確には「量子コンピューターで」の部分は嘘だ。量子原理を使った計算機の中にはゲート型というものと量子イジングマシンというものとがあり、プロフェッショナルは後者のことを「量子コンピューター」とは呼ばないらしい。不正確な理解だけど、素因数分解を高速にできるショアのアルゴリズムなんかは後者では動かないんじゃないかな？さらには、量子イジングマシンの中にも、D-WAVEのようなちゃんと量子効果を使っているものもあれば、GPUを使ってシミュレートだけを行っているものもある。プロフェッショナルは「量子じゃないこと」を「古典的」と呼ぶので、後者のことは古典的イジングマシンとでも呼べばいいのだろうか。ともかく、今回は古典的なイジングマシンを使ってプログラミングを行う。

８クイーン問題について

　まず、８クイーン問題について説明する。このパズルは、チェスのクイーンの駒を8×8の盤面上に並べるものである。ただし、クイーンの「利き」がある範囲に、別のクイーンを配置することはできない。クイーンはチェスの駒の中では最大の範囲を持ち、縦横斜めの８方向に任意に動くことができる。将棋の飛車と角を合わせた範囲だ。だから、64マスに8個の駒を並べるというのは想像以上に難しい。なお、wikipedia先生(エイト・クイーン - Wikipedia)によると、盤面を回転したり反転したりして得られるトリビアルなものを除けば、12個の解法が存在するらしい。
　８クイーン問題における、クイーンの配置の条件をもう少し解きほぐしてみよう。まず、クイーンが縦横に任意に移動できることから、同じ行と列に2人のクイーンは存在できない(図1)。逆に言うと、行も列も8つずつあるから、ある行または列には最低1人のクイーンが居座ることになる。正解の盤面を側面から眺めると、8人のクイーンが重なりなく並んでいるように見えるだろう。以降、この行と列の条件を、条件①と②と呼ぼう。また、斜めにも任意に移動できるため、斜め方向にも2人以上のクイーンを置くことができない(図1)。以降、この斜めの条件を、条件③と呼ぼう。つまり、
条件①　1つの行には必ず1人のクイーンがいる。
条件②　1つの列には必ず1人のクイーンがいる。
条件③　斜め方向には最大で1人のクイーンがいる。
という条件が定式化されたことになる。

Amplifyについて

　次に、今回のプログラミングで用いるAmplifyというフレームワークについて紹介したい。これは、Fixstars社から提供されているもので、pythonで書かれたコードによるイジングマシンの操作を可能にする。使用可能なイジングマシンは複数用意されているが、無料プランではFixstarsが用意したGPUによるイジングマシンと、D-WAVEの量子イジングマシンが使えるようである。ただし、『月刊インターフェース』の記事では、D-WAVEの使用時間は1月あたり3分とのことであった。Fixstarsのページ(実行環境 - Amplify - 量子アニーリングと共に進化するクラウド)には、東芝のデジタルアニーラなんかも使用可能マシンとして紹介されていたけれど、こちらは有料プランということだろうか？ちゃんと理解をしていない。いずれにしても、今回はFixstarsのイジングマシンを利用してプログラミングを行う。
　Amplifyのプログラミングは、基本的には①最適化するための変数の定義、②目的関数や制約条件の変数による記述、③マシンを指定して最適化の実行、の3ステップである。通常のプログラミングでは、対象とする最適化問題ごとに適したアルゴリズムをコード化する必要がある。しかし、Amplifyのプログラミングでは、とにかく目的関数や制約条件を指定すればそれで充分である。そのため、プログラミングが非常に簡便になる。ただし、イジングマシンによる計算結果が通常のコンピュータによる計算結果より高速であるとは限らないという点には注意が必要だ。
　また、イジングマシンの性質上、答えが「あり/なし」のように、1/0の2値で記述される問題に適している。そうでない問題、例えば最適な原料の割合を導き出せ、みたいな問題も解けないことは無いけれど、一工夫が必要であるように感じた。もしかしたら、僕が勉強不足なだけかもしれないけど。

ソースコードの解説

　それでは、ソースコードの紹介に移っていきたいと思う。なお、今回のプログラミングは、ブラウザ上でpythonのプログラミングを行える、Google Colaboratoryを利用した。こちらも『月刊インターフェース』で初めて知ったけど、便利な世の中になったなぁと感じる。なお、恥ずかしい話であるが、プログラミングが非効率的であったり、用語の使用が間違ったりしている可能性が大いにある。その際には見逃していただくか、ご指摘いただけると幸いである。
　まず、Amplifyを使うために、「pip install amplify」によりインストールを実行しておく。

import matplotlib.pyplot as plt

from amplify import (BinaryPoly, sum_poly, Solver, SymbolGenerator) 
from amplify.constraint import (equal_to, less_equal)
from amplify.client import FixstarsClient

client = FixstarsClient()
client.token = 'xxxx'

　この部分では、プログラミングに必要なAmplifyのモジュールの他、結果を描写するためのmatplotlibをインストールしている。”client.token =”の後には、Fixstars Amplifyに会員登録をした後に発行されるトークンをコピペで張り付けておく。

gen = SymbolGenerator(BinaryPoly)
q = gen.array(8,8)

　ここでは、クイーンの位置を表現するための変数を定義している。前述のように、Amplifyのプログラミングでは、0か1の値をとるバイナリ変数か、-1か1の値をとるイジング変数を使用する。今回は、チェスの盤面の各マスにバイナリ変数を割り当て、クイーンがいるマスでは1、そうでないマスでは0の値を取るようにする。なお、以降では行を表す添え字に $i$ 、列を表す添え字に $j$ を用いる。これらの添え字は0から7の値を取る。文章中では、 $i$ 行 $j$ 列のマスに対応する変数を $q_{i,j}$ と表現する。

const_row = [equal_to(sum_poly(q[i, :]), 1) for i in range(8)]
const_col = [equal_to(sum_poly(q[:, j]), 1) for j in range(8)]

const_right_diag 
  = [less_equal(sum_poly([q[i, k - i] for i in range(k + 1)]), 1) for k in range(8)]
    + [less_equal(sum_poly([q[7 - i, 7 + i - k] for i in range (k + 1)]), 1) for k in range(7)]
const_left_diag
  = [less_equal(sum_poly([q[i, 7 + i - k] for i in range (k + 1)]), 1) for k in range(8)]
    + [less_equal(sum_poly([q[7 - i, k - i] for i in range (k + 1)]), 1) for k in range(7)]

constraints = sum(const_row) + sum(const_col) + sum(const_right_diag) + sum(const_left_diag)

ここでは、制約条件を定義する。なお、8クイーン問題では制約条件を満足しさえすればいいので、目的関数は使用しない。先に述べた通り、8クイーン問題は条件①～③の3つの条件が満足される必要がある。これらの条件を、バイナリ変数 $q_{i,j}$ で表現できれば、Amplifyのプログラミングの9割は終わったも同然だ。

行に関する制約条件①は、「1つの行には必ず1人のクイーンがいる」というものであった。この条件を言い換えると、ある固定されたiの変数 $q_{i,j}$ の内、ただ一つだけが1であり、後は0である、ということになる。この条件は、数式により非常に簡単に

$\displaystyle{ \sum_{j=0}^7 q_{i,j} =1}\\$

となる。と表現できる。この条件をAmplify風に書き直すと、ソースコード中の

equal_to(sum_poly(q[i, :]), 1)

という表現になる。Amplifyで使うバイナリ変数の合計を計算するには、Amplifyの組み込み関数であるsum_poly関数を用いる。pythonの普通のsum関数を使えるらしいけど、sum_poly関数より低速になるらしい。試してないから分からないけど。あと、等しいという制約条件も、いつものイコール2つ(==)で結ぶのではなくて、組み込み関数equal_toを使用する。この条件を7つのiに対して設定するためには、通常のpythonと同様に内包表記でfor文を走らせればよい。
　同様に、列に関する制約条件②、「1つの列には必ず1人のクイーンがいる」は

$\displaystyle{ \sum_{i=0}^7 q_{i,j} =1}\\$

と表現される。シグマ記号の下の添え字に注意されたい。ソースコードでの表現は

equal_to(sum_poly(q[:, j]), 1)

のようになる。
　制約条件③、「斜め方向には最大で1人のクイーンがいる。」も、列と行の条件と同様に変数の合計をなんとかするアプローチで攻めていくが、多少複雑になる。まず、行と列の条件は全部で16個あるが、斜めの数は合計で30個もある。図2に示すように、右上から左下方向のラインが合計で15本あり、同様に左上から右下方向のラインも15本あるからだ。また、右上から左下方向のラインも、左上側の8本のラインと、右下側の7本のラインに分けて考えた方が見通しが良い。

　最初に、左上側の8本のラインを考える。図2の緑色の線に示すように、マスが一つずつ増えていく方向で、 $k=0$ から $k=7$ の添え字を振っていく。この添え字における変数 $q_{i,j}$ の合計に関する条件を露わに書き下すと、

$\displaystyle{q_{0,0} \le 1} \\ \displaystyle{q_{0,1} + q_{1,0} \le 1} \\ \displaystyle{q_{0,2} + q_{1,1} + q_{2,0} \le 1} \\ \displaystyle{q_{0,3} + q_{1,2} + q_{2,1} + q_{3,0} \le 1} \\ \displaystyle{q_{0,4} + q_{1,3} + q_{2,2} + q_{3,1} + q_{4,0} \le 1} \\ \displaystyle{q_{0,5} + q_{1,4} + q_{2,3} + q_{3,2} + q_{4,1} + q_{5,0} \le 1} \\ \displaystyle{q_{0,6} + q_{1,5} + q_{2,4} + q_{3,3} + q_{4,2} + q_{5,1} + q_{6,0} \le 1} \\ \displaystyle{q_{0,7} + q_{1,6} + q_{2,5} + q_{3,4} + q_{4,3} + q_{5,2} + q_{6,1} + q_{7,0} \le 1}\\$

のようになる。これまでの条件と違って、右辺は不等式となる。これは、クイーンがいない斜めの方向も許されるからである。別にこのままこれらの条件を使ってもいいのだけど、将来の一般化を考えると、何かしらの一般式で表せるようにしておきたい。各添え字に注目すると、その合計は式ごとに等しく、条件の番号 $k$ と等しくなる。この事実を利用すると、

$\displaystyle{ \sum_{i=0}^k q_{i,k-i} \le 1}\\$

という一般式が得られる。
　次に、右下の7本のラインを考える。こちらも、図2の青色の線に示すように、マスが一つずつ増えていく方向で、 $k' = 0$ から $k' = 7$ の添え字を振っていく。そして、各添え字 $k'$ に対する条件を書き下すと、

$\displaystyle{q_{7,7} \le 1} \\ \displaystyle{q_{6,7} + q_{7,6} \le 1} \\ \displaystyle{q_{5,7} + q_{6,6} + q_{7,5} \le 1} \\ \displaystyle{q_{4,7} + q_{5,6} + q_{6,5} + q_{7,4} \le 1} \\ \displaystyle{q_{3,7} + q_{4,6} + q_{5,5} + q_{6,4} + q_{7,3} \le 1} \\ \displaystyle{q_{2,7} + q_{3,6} + q_{4,5} + q_{5,4} + q_{6,3} + q_{7,2} \le 1} \\ \displaystyle{q_{1,7} + q_{2,6} + q_{3,5} + q_{4,4} + q_{5,3} + q_{6,2} + q_{7,1} \le 1} \\$

という7つの条件式が得られる。この条件式の一般形を得るために、左上の条件式と右下の条件式を見比べてみよう。すると、添え字の間にある種の関係があることが分かる。つまり、添え字 $k$ に対応する左上の条件式の各項の添え字を7から引くと、添え字 $k'=k$ に対応する右下の条件式が得られる。例えば、 $k=2$ に対応する左上の条件式

$\displaystyle{q_{0,2}+q_{1,1}+q_{2,0} \le 1} \\$

の各項の添え字から7を引くと、 $k'=2$ に対応する右下の条件式

$\displaystyle{q_{5,7}+q_{6,6}+q_{7,5} \le 1} \\$

が得られるといった具合である。この事実を利用すると、右下の条件の一般形は

$\displaystyle{ \sum_{i=0}^{k'} q_{7-i,7-k'+i} \le 1}\\$

と、求まる。Amplifyのソースでこれらの条件を表現すると、

  less_equal(sum_poly([q[i, k-i] for i in range (k + 1)]), 1)
  less_equal(sum_poly([q[7-i, 7-k+i] for i in range (k + 1)]), 1)

となる。関数less_equalが、Amplifyにおける不等式条件を表すとなっている。
　同様にして、左上から右下方向のラインの15個の条件も1

$\displaystyle{ \sum_{i=0}^k q_{i,7-k+i} \le 1}\\$

と(ただし、 $k$ は0から7の範囲)、

$\displaystyle{ \sum_{i=0}^{k'} q_{7-i,k'-i} \le 1}\\$

のように求められる(ただし、 $k'$ は0から６の範囲)。
　以上のように、合計で46個の制約条件が得られたが、最後にそれらを合計する。イジングマシンは、制約条件の（と目的関数の）合計が小さくなるような変数の組み合わせを探す。

client.parameters.timeout = 1000

solver = Solver(client)
results = solver.solve(constraints)

q_values = q.decode(results[0].values)
answer = q_values.nonzero()

　この部分がいよいよ計算を実行する部分だ。実行時間を1000ミリ秒に設定し、上記で定めた制約条件の下でソルバーを走らせる。そして、その答えをanswerという変数に格納する。answerは8×8の行列で、クイーンがいるところだけが1となっている。

fig = plt.figure(figsize=(10,10))
ax = fig.add_subplot(111)

for i in range(7):
  ax.axvline(0.5 + i, lw = 2, c = 'k')
  ax.axhline(0.5 + i, lw = 2, c = 'k')

ax.imshow(q_values, "Reds")

この部分が解答を可視化するプログラムである。1のマス目、すなわちクイーンのいるマス目が濃い目の赤色になるように、0と1のバイナリ行列を色分けで表現する。図3に実際にここまでのプログラムを走らせて得られた答えを提示する。この通り、各クイーンの「利き」が重ならないように配置されている。なお、先述の通り8クイーン問題は12個の解答が存在する。トリビアルなものを含めると92個になる。イジングマシンは制約条件を見たいしている解答のみを出力するので、このプログラムも92個の解答をランダムに出力する。

おわりに

　さて、今回はイジングモデルを用いて8クイーン問題を解いてみた。次回以降は8の数字を様々変えてみたいと考えている。こういった一般化された8クイーン問題はNクイーン問題と呼ばれている。今回のプログラムは、このNクイーン問題への拡張を容易にすることを企図して組まれている。また、この8クイーン問題に限らず、その他の組み合わせ最適化問題も様々試している。最終的には実社会の問題の解決にこういったものを使っていきたいなぁと思っているが、そんな問題はなかなか見つからない。でも、そこまでできたら俺はもうこれで飯を食っていけちゃうよなぁ、なんてにやにやしている。

ふくろうの本棚

ふくろうには似ても似つかない限界独身男性が色んなことを書きます

8クイーン問題をイジングマシンで解いてみた

８クイーン問題について

Amplifyについて

ソースコードの解説

おわりに