(2018年11月追記)※wildcatは現在、記事執筆当初から大きく仕様やAPIが変わっています。最新版にも移植しましたので、こちらの記事もご覧ください。
#wildcatってなんだ?
Wildcatとは、量子コンピュータ系ベンチャーのMDR社が開発した量子アニーリングっぽい問題を解くためのライブラリで、MDR社のAPIを叩いて結果を取ってくる仕組みになっています。
今のところは、登録不要でサーバが落ちない程度試せる、らしいです。
https://github.com/mdrft/wildcat
pipでインストールする方法も書かれていますが、まだできたばかりなので更新が多いかもしれないと思って、git cloneして、同じディレクトリにJupyter Notebook作ってやってます。
#解きたい問題
手始めに、4x4の数独を解かせてみました。
解く問題は、次の問題とします。
1? ??
?? 2?
?3 ??
?? ?4
ちなみに、答えは
12 43
34 21
43 12
21 34
になります。
#量子アニーリングで数独、どう解く？
QUBOという形に落とし込んで解きます。
量子アニーリングやQUBOについては
量子アニーリング、イジングモデルとフレームワーク
QUBOを使って日本地図の彩色問題やってみた
を参照ください。
#QUBOを作る
QUBOとは
H=\sum_{i,j}Q_{ij}x_ix_j
の、Hを最小にするように $x_i \in { 0, 1 }$ を発見する最適化問題でした。
QUBOを作るときに考えないといけないのは、 $x_i$ とは何を表現する量か、そのためにQをどのようにしたらいいか、です。
xiで何を表現するか
まず、4x4のマス目に数字を割り振ります。
0 1 | 2 3
4 5 | 6 7
------+-------
8 9 | 10 11
12 13 | 14 15
$x_i$ に、好きな整数を入れられたら、これで終わるのですが、 $x_i$ は0か1しか入らないので、 $x_i$ は次のようにします。
i = 0..15: $x_i$ が1のとき、マス目iに数字1が入っている
i = 16..31: $x_i$ が1のとき、マス目(i-16)に数字2が入っている
i = 32..47: $x_i$ が1のとき、マス目(i-32)に数字3が入っている
i = 48..63: $x_i$ が1のとき、マス目(i-48)に数字4が入っている
このように、 $x_0$ から $x_{63}$ を定めることにします。
##Qをどう作るか
ナンプレの制約条件は、以下のように言えます。
- 全部のマス目を埋めること。?のままは許されない
- ひとつのマス目には、ひとつしか数字が入らない
- 同じ列に、同じ数字がないこと
- 同じ行に、同じ数字がないこと
- 同じブロックに、同じ数字がないこと
- 最初から問題文に書かれている数字は書き換えないこと
これらの条件を守ったときに $H=\sum_{i,j}Q_{ij}x_ix_j$ が最小となるよう、Qを作成します。
下準備として、行、列、ブロックや問題文を作っておきます。
n = 4**3
grouping = [
# rows
[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11],
[12, 13, 14, 15],
# columns
[ 0, 4, 8, 12],
[ 1, 5, 9, 13],
[ 2, 6, 10, 14],
[ 3, 7, 11, 15],
# blocks
[ 0, 1, 4, 5],
[ 2, 3, 6, 7],
[ 8, 9, 12, 13],
[10, 11, 14, 15],
]
problem_str = '1?????2??3?????4'
続いて、QUBOを作っていきます。
# なにか数字を埋めると報酬(Hが小さくなる)がもらえるようにする
qubo = np.eye(n) * -1
# 行、列、ブロックに同じ数字があったら、ペナルティ(Hが大きくなる)を与えるようにする
for g in grouping:
for i in range(4):
for j in range(3):
for k in range(j+1, 4):
qubo[i*16 + g[j], i*16 + g[k]] += 2
# 同じマスには別の数字が入らないようにペナルティを与える
for i in range(16):
for j in range(3):
for k in range(j+1, k):
qubo[i+j*16, i+k*16] += 2.5
# 既に問題文に数字が入っている場合、そこには別の数字を入れないように報酬やペナルティを調整する
for i, v in enumerate(problem_str):
if v == '?':
continue
v = int(v) - 1
qubo[v*16 + i, v*16 + i] -= 20
for j in range(4):
qubo[j*16 + i, j*16 + i] += 4
for g in grouping:
if i not in g:
continue
for j in g:
qubo[v*16 + j, v*16 + j] += 3 + v*0.3
いろいろと係数が入っていますが、正直、勘でやっています。今のがベストじゃない可能性も多いにあります。
符号が逆じゃないこと、制約を無視した最適化が行われないことは必須ですが、そうならない範囲で、いろいろと調整の余地はあるはずなのです。
#wildcatで解く
次のように、WildcatにQUBOを渡します。
from wildcat.util.matrix import random_symmetric_matrix
from wildcat.solver.qubo_solver import QuboSolver
solver = QuboSolver(qubo)
foo = None
def callback(arrangement):
global foo
foo = arrangement
print(sum(foo>0))
solver.solve(callback).result()
なお、solver.solveはFutureオブジェクトを返します。また、計算が終わるとcallbackを呼び出します。
本来は非同期のお作法に従うといいのですが、Jupyter Notebookなどで試す場合には、こんなもんでいいのかな、と思います。
#結果
board = ['?'] * 16
for i,b in enumerate(foo.tolist()):
if b == 1:
#if board[i%16] != '?':
# print('!', end='')
board[i%16] = (i//16) + 1
print('''{}{} {}{}
{}{} {}{}
{}{} {}{}
{}{} {}{}'''.format(*board))
とすると、
12 43
34 21
43 12
21 34
が表示されるはずです。
が、実際には、たまにしか完答できません。
アニーリングによる最適化は割と運ゲーなのと、Qのところの係数の調整がまだ甘かったりするようで、何度か QuboSolver を動かしていると、そのうち答えが合うはずです。
#ノートブックはこちら
https://github.com/gyu-don/wildcat/blob/master/Number%20Place%204x4.ipynb