wildcatで4x4の数独を解いてみた

**(2018年11月追記)※wildcatは現在、記事執筆当初から大きく仕様やAPIが変わっています。最新版にも移植しましたので、[こちらの記事](https://qiita.com/gyu-don/items/dbe005fd5099bfd8e946)もご覧ください。**

#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については
[量子アニーリング、イジングモデルとフレームワーク](https://qiita.com/YuichiroMinato/items/e6952fec1a9965156873)
[QUBOを使って日本地図の彩色問題やってみた](https://qiita.com/gyu-don/items/dc83392cb890db6c8d61)
を参照ください。

#QUBOを作る
QUBOとは

```math
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を作成します。

下準備として、行、列、ブロックや問題文を作っておきます。

```py3
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を作っていきます。

```py3
# なにか数字を埋めると報酬(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を渡します。

```py3
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オブジェクト](https://docs.python.jp/3/library/concurrent.futures.html#future-objects)を返します。また、計算が終わるとcallbackを呼び出します。
本来は非同期のお作法に従うといいのですが、Jupyter Notebookなどで試す場合には、こんなもんでいいのかな、と思います。

#結果
```py3
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