概要
エイト・クイーン問題はチェス盤とチェスの駒（クイーン）を使ったパズルである。
クイーンは盤上の上下左右斜めの8方向に遮る駒がない限り移動できる。エイト・クイーン問題は、チェスの盤（8×8）に8個のクイーンを配置するときに、全てのクイーンが互いのクイーンに取られないような配置を探索するものである。詳しくはエイト・クイーン問題を参照。
この記事では、qbsolvを使って実際にエイト・クイーン問題を解く方法について解説する。なお、本記事はqbsolvのインストール手順や使用方法の詳細については省略する。また、タイトルでは「アニーリングマシンで解いてみる」とあるが、実際にはシミュレーションによって解を求めているだけで、実際に（dwaveなどの）アニーリングマシンを利用しているわけではない。
2018.08.26 追記 イジングモデル構築過程に問題があったため内容を修正。
準備
イジングモデルの構築
イジングモデルのQUBO変数$q$は、チェス盤の1マスに対応させる。チェス盤は64マス（8×8）であるため計64個のQUBO変数を用意する。
q_{k} \equiv q_{8i + j} \in \{0, 1\}, \quad i, j \in \{ 0, \,1, \cdots, 7 \} ,\,\, k \in \{ 0, 1, \cdots, 63 \}
$i$はチェス盤の行番号（一番上の行が0、一番下の行が7）、$j$は列番号（一番左の列が0、一番右の列が7）を表すものとする。$q=0$はマスにクイーンを配置していない状態、$q=1$はクイーンを配置している状態を表現する。この問題では、8×8の盤面にクイーンを8個置かなければならないため、必ずすべての行・列に1つずつクイーンが配置されなければならない。この制約条件は、以下のように表される。
\sum _{i} q_{8i + k} = 1, \quad \sum _{j} q_{8k + j} = 1
これをハミルトニアンに変換すると、
H _{0} = \sum _{k} \left( 1 - \sum _{i} q_{8i+k} \right) ^{2} + \sum _{k} \left( 1 - \sum _{j} q_{8k + j} \right) ^{2}
となる。また、$q=1$のマスの斜め4方向に存在するマスは全て$q=0$でなければならない。あるマスに対応するQUBO変数$q_{k} \equiv q_{8i + j}$と斜め4方向に存在するQUBO変数がともに1である場合に、エネルギーが増加するようにハミルトニアンを構成すればよいので、この制約事項に対応したハミルトニアンは以下のように書ける。
H^{(i, j)} = \sum _{s \in S_{i, j}} q_{s} q_{8i+j}
ただし、$S_{i, j}$は$q_{8i+j}$のマスの左上、右上の2方向に存在するマスに対応するQUBO変数のインデックスの集合である。下図の青色マスに対して、黄色マスが$S_{i, j}$に該当する。
$H^{(i, j)}$の足し合わせでハミルトニアンを構成すればよいので、ハミルトニアンは以下のように書ける。エネルギーの最小値を取るQUBO変数の配置には影響しないため、定数項は無視する。
\begin{align}
H &= H_{0} + \sum _{i} \sum _{j} H^{(i, j)} \\
&= \sum _{k} \left( 1 - \sum _{i} q_{8i+k} \right) ^{2} +
\sum _{k} \left( 1 - \sum _{j} q_{8k+j} \right) ^{2} + \sum _{i} \sum _{j} \sum _{s \in S_{i, j}} q_{s} q_{8i+j} \\
&= \sum _{k} \left( 1 - \sum _{i} q_{8i+k} + 2 \sum _{i < l} q_{8i+k}q_{8l+k} \right) +
\sum _{k} \left( 1 - \sum _{j} q_{8k+j} + 2 \sum _{j < l} q_{8k+j}q_{8k+l} \right) + \sum _{i} \sum _{j} \sum _{s \in S_{i, j}} q_{s} q_{8i+j} \\
&= 16 - 2 \sum _{i} \sum _{j} q_{8i+j} + 2 \left( \sum _{i < l} q_{8i+k}q_{8l+k} + \sum _{j < l} q_{8k+j}q_{8k+l} \right) + \sum _{i} \sum _{j} \sum _{s \in S_{i, j}} q_{s} q_{8i+j} \\
& \longrightarrow - 2 \sum _{i} \sum _{j} q_{8i+j} + 2 \left( \sum _{i < l} q_{8i+k}q_{8l+k} + \sum _{j < l} q_{8k+j}q_{8k+l} \right) + \sum _{i} \sum _{j} \sum _{s \in S_{i, j}} q_{s} q_{8i+j}
\end{align}
QUBOファイル作成
上記ハミルトニアンから、QUBOファイルを作成する。ノード数はチェス盤のマス数と同じであるため64である。カプラ（ノード間の結合）数は、728である。
QUBOファイル例
c
p qubo 0 64 64 728
c
0 0 -2.0
1 1 -2.0
2 2 -2.0
3 3 -2.0
4 4 -2.0
5 5 -2.0
6 6 -2.0
7 7 -2.0
8 8 -2.0
9 9 -2.0
10 10 -2.0
11 11 -2.0
12 12 -2.0
13 13 -2.0
14 14 -2.0
15 15 -2.0
16 16 -2.0
17 17 -2.0
18 18 -2.0
19 19 -2.0
20 20 -2.0
21 21 -2.0
22 22 -2.0
23 23 -2.0
24 24 -2.0
25 25 -2.0
26 26 -2.0
27 27 -2.0
28 28 -2.0
29 29 -2.0
30 30 -2.0
31 31 -2.0
32 32 -2.0
33 33 -2.0
34 34 -2.0
35 35 -2.0
36 36 -2.0
37 37 -2.0
38 38 -2.0
39 39 -2.0
40 40 -2.0
41 41 -2.0
42 42 -2.0
43 43 -2.0
44 44 -2.0
45 45 -2.0
46 46 -2.0
47 47 -2.0
48 48 -2.0
49 49 -2.0
50 50 -2.0
51 51 -2.0
52 52 -2.0
53 53 -2.0
54 54 -2.0
55 55 -2.0
56 56 -2.0
57 57 -2.0
58 58 -2.0
59 59 -2.0
60 60 -2.0
61 61 -2.0
62 62 -2.0
63 63 -2.0
0 1 2.0
1 2 2.0
0 2 2.0
2 3 2.0
1 3 2.0
0 3 2.0
3 4 2.0
2 4 2.0
1 4 2.0
0 4 2.0
4 5 2.0
3 5 2.0
2 5 2.0
1 5 2.0
0 5 2.0
5 6 2.0
4 6 2.0
3 6 2.0
2 6 2.0
1 6 2.0
0 6 2.0
6 7 2.0
5 7 2.0
4 7 2.0
3 7 2.0
2 7 2.0
1 7 2.0
0 7 2.0
0 8 2.0
1 8 1.0
1 9 2.0
8 9 2.0
0 9 1.0
2 9 1.0
2 10 2.0
9 10 2.0
8 10 2.0
1 10 1.0
3 10 1.0
3 11 2.0
10 11 2.0
9 11 2.0
8 11 2.0
2 11 1.0
4 11 1.0
4 12 2.0
11 12 2.0
10 12 2.0
9 12 2.0
8 12 2.0
3 12 1.0
5 12 1.0
5 13 2.0
12 13 2.0
11 13 2.0
10 13 2.0
9 13 2.0
8 13 2.0
4 13 1.0
6 13 1.0
6 14 2.0
13 14 2.0
12 14 2.0
11 14 2.0
10 14 2.0
9 14 2.0
8 14 2.0
5 14 1.0
7 14 1.0
7 15 2.0
14 15 2.0
13 15 2.0
12 15 2.0
11 15 2.0
10 15 2.0
9 15 2.0
8 15 2.0
6 15 1.0
8 16 2.0
0 16 2.0
9 16 1.0
2 16 1.0
9 17 2.0
1 17 2.0
16 17 2.0
8 17 1.0
10 17 1.0
3 17 1.0
10 18 2.0
2 18 2.0
17 18 2.0
16 18 2.0
9 18 1.0
0 18 1.0
11 18 1.0
4 18 1.0
11 19 2.0
3 19 2.0
18 19 2.0
17 19 2.0
16 19 2.0
10 19 1.0
1 19 1.0
12 19 1.0
5 19 1.0
12 20 2.0
4 20 2.0
19 20 2.0
18 20 2.0
17 20 2.0
16 20 2.0
11 20 1.0
2 20 1.0
13 20 1.0
6 20 1.0
13 21 2.0
5 21 2.0
20 21 2.0
19 21 2.0
18 21 2.0
17 21 2.0
16 21 2.0
12 21 1.0
3 21 1.0
14 21 1.0
7 21 1.0
14 22 2.0
6 22 2.0
21 22 2.0
20 22 2.0
19 22 2.0
18 22 2.0
17 22 2.0
16 22 2.0
13 22 1.0
4 22 1.0
15 22 1.0
15 23 2.0
7 23 2.0
22 23 2.0
21 23 2.0
20 23 2.0
19 23 2.0
18 23 2.0
17 23 2.0
16 23 2.0
14 23 1.0
5 23 1.0
16 24 2.0
8 24 2.0
0 24 2.0
17 24 1.0
10 24 1.0
3 24 1.0
17 25 2.0
9 25 2.0
1 25 2.0
24 25 2.0
16 25 1.0
18 25 1.0
11 25 1.0
4 25 1.0
18 26 2.0
10 26 2.0
2 26 2.0
25 26 2.0
24 26 2.0
17 26 1.0
8 26 1.0
19 26 1.0
12 26 1.0
5 26 1.0
19 27 2.0
11 27 2.0
3 27 2.0
26 27 2.0
25 27 2.0
24 27 2.0
18 27 1.0
9 27 1.0
0 27 1.0
20 27 1.0
13 27 1.0
6 27 1.0
20 28 2.0
12 28 2.0
4 28 2.0
27 28 2.0
26 28 2.0
25 28 2.0
24 28 2.0
19 28 1.0
10 28 1.0
1 28 1.0
21 28 1.0
14 28 1.0
7 28 1.0
21 29 2.0
13 29 2.0
5 29 2.0
28 29 2.0
27 29 2.0
26 29 2.0
25 29 2.0
24 29 2.0
20 29 1.0
11 29 1.0
2 29 1.0
22 29 1.0
15 29 1.0
22 30 2.0
14 30 2.0
6 30 2.0
29 30 2.0
28 30 2.0
27 30 2.0
26 30 2.0
25 30 2.0
24 30 2.0
21 30 1.0
12 30 1.0
3 30 1.0
23 30 1.0
23 31 2.0
15 31 2.0
7 31 2.0
30 31 2.0
29 31 2.0
28 31 2.0
27 31 2.0
26 31 2.0
25 31 2.0
24 31 2.0
22 31 1.0
13 31 1.0
4 31 1.0
24 32 2.0
16 32 2.0
8 32 2.0
0 32 2.0
25 32 1.0
18 32 1.0
11 32 1.0
4 32 1.0
25 33 2.0
17 33 2.0
9 33 2.0
1 33 2.0
32 33 2.0
24 33 1.0
26 33 1.0
19 33 1.0
12 33 1.0
5 33 1.0
26 34 2.0
18 34 2.0
10 34 2.0
2 34 2.0
33 34 2.0
32 34 2.0
25 34 1.0
16 34 1.0
27 34 1.0
20 34 1.0
13 34 1.0
6 34 1.0
27 35 2.0
19 35 2.0
11 35 2.0
3 35 2.0
34 35 2.0
33 35 2.0
32 35 2.0
26 35 1.0
17 35 1.0
8 35 1.0
28 35 1.0
21 35 1.0
14 35 1.0
7 35 1.0
28 36 2.0
20 36 2.0
12 36 2.0
4 36 2.0
35 36 2.0
34 36 2.0
33 36 2.0
32 36 2.0
27 36 1.0
18 36 1.0
9 36 1.0
0 36 1.0
29 36 1.0
22 36 1.0
15 36 1.0
29 37 2.0
21 37 2.0
13 37 2.0
5 37 2.0
36 37 2.0
35 37 2.0
34 37 2.0
33 37 2.0
32 37 2.0
28 37 1.0
19 37 1.0
10 37 1.0
1 37 1.0
30 37 1.0
23 37 1.0
30 38 2.0
22 38 2.0
14 38 2.0
6 38 2.0
37 38 2.0
36 38 2.0
35 38 2.0
34 38 2.0
33 38 2.0
32 38 2.0
29 38 1.0
20 38 1.0
11 38 1.0
2 38 1.0
31 38 1.0
31 39 2.0
23 39 2.0
15 39 2.0
7 39 2.0
38 39 2.0
37 39 2.0
36 39 2.0
35 39 2.0
34 39 2.0
33 39 2.0
32 39 2.0
30 39 1.0
21 39 1.0
12 39 1.0
3 39 1.0
32 40 2.0
24 40 2.0
16 40 2.0
8 40 2.0
0 40 2.0
33 40 1.0
26 40 1.0
19 40 1.0
12 40 1.0
5 40 1.0
33 41 2.0
25 41 2.0
17 41 2.0
9 41 2.0
1 41 2.0
40 41 2.0
32 41 1.0
34 41 1.0
27 41 1.0
20 41 1.0
13 41 1.0
6 41 1.0
34 42 2.0
26 42 2.0
18 42 2.0
10 42 2.0
2 42 2.0
41 42 2.0
40 42 2.0
33 42 1.0
24 42 1.0
35 42 1.0
28 42 1.0
21 42 1.0
14 42 1.0
7 42 1.0
35 43 2.0
27 43 2.0
19 43 2.0
11 43 2.0
3 43 2.0
42 43 2.0
41 43 2.0
40 43 2.0
34 43 1.0
25 43 1.0
16 43 1.0
36 43 1.0
29 43 1.0
22 43 1.0
15 43 1.0
36 44 2.0
28 44 2.0
20 44 2.0
12 44 2.0
4 44 2.0
43 44 2.0
42 44 2.0
41 44 2.0
40 44 2.0
35 44 1.0
26 44 1.0
17 44 1.0
8 44 1.0
37 44 1.0
30 44 1.0
23 44 1.0
37 45 2.0
29 45 2.0
21 45 2.0
13 45 2.0
5 45 2.0
44 45 2.0
43 45 2.0
42 45 2.0
41 45 2.0
40 45 2.0
36 45 1.0
27 45 1.0
18 45 1.0
9 45 1.0
0 45 1.0
38 45 1.0
31 45 1.0
38 46 2.0
30 46 2.0
22 46 2.0
14 46 2.0
6 46 2.0
45 46 2.0
44 46 2.0
43 46 2.0
42 46 2.0
41 46 2.0
40 46 2.0
37 46 1.0
28 46 1.0
19 46 1.0
10 46 1.0
1 46 1.0
39 46 1.0
39 47 2.0
31 47 2.0
23 47 2.0
15 47 2.0
7 47 2.0
46 47 2.0
45 47 2.0
44 47 2.0
43 47 2.0
42 47 2.0
41 47 2.0
40 47 2.0
38 47 1.0
29 47 1.0
20 47 1.0
11 47 1.0
2 47 1.0
40 48 2.0
32 48 2.0
24 48 2.0
16 48 2.0
8 48 2.0
0 48 2.0
41 48 1.0
34 48 1.0
27 48 1.0
20 48 1.0
13 48 1.0
6 48 1.0
41 49 2.0
33 49 2.0
25 49 2.0
17 49 2.0
9 49 2.0
1 49 2.0
48 49 2.0
40 49 1.0
42 49 1.0
35 49 1.0
28 49 1.0
21 49 1.0
14 49 1.0
7 49 1.0
42 50 2.0
34 50 2.0
26 50 2.0
18 50 2.0
10 50 2.0
2 50 2.0
49 50 2.0
48 50 2.0
41 50 1.0
32 50 1.0
43 50 1.0
36 50 1.0
29 50 1.0
22 50 1.0
15 50 1.0
43 51 2.0
35 51 2.0
27 51 2.0
19 51 2.0
11 51 2.0
3 51 2.0
50 51 2.0
49 51 2.0
48 51 2.0
42 51 1.0
33 51 1.0
24 51 1.0
44 51 1.0
37 51 1.0
30 51 1.0
23 51 1.0
44 52 2.0
36 52 2.0
28 52 2.0
20 52 2.0
12 52 2.0
4 52 2.0
51 52 2.0
50 52 2.0
49 52 2.0
48 52 2.0
43 52 1.0
34 52 1.0
25 52 1.0
16 52 1.0
45 52 1.0
38 52 1.0
31 52 1.0
45 53 2.0
37 53 2.0
29 53 2.0
21 53 2.0
13 53 2.0
5 53 2.0
52 53 2.0
51 53 2.0
50 53 2.0
49 53 2.0
48 53 2.0
44 53 1.0
35 53 1.0
26 53 1.0
17 53 1.0
8 53 1.0
46 53 1.0
39 53 1.0
46 54 2.0
38 54 2.0
30 54 2.0
22 54 2.0
14 54 2.0
6 54 2.0
53 54 2.0
52 54 2.0
51 54 2.0
50 54 2.0
49 54 2.0
48 54 2.0
45 54 1.0
36 54 1.0
27 54 1.0
18 54 1.0
9 54 1.0
0 54 1.0
47 54 1.0
47 55 2.0
39 55 2.0
31 55 2.0
23 55 2.0
15 55 2.0
7 55 2.0
54 55 2.0
53 55 2.0
52 55 2.0
51 55 2.0
50 55 2.0
49 55 2.0
48 55 2.0
46 55 1.0
37 55 1.0
28 55 1.0
19 55 1.0
10 55 1.0
1 55 1.0
48 56 2.0
40 56 2.0
32 56 2.0
24 56 2.0
16 56 2.0
8 56 2.0
0 56 2.0
49 56 1.0
42 56 1.0
35 56 1.0
28 56 1.0
21 56 1.0
14 56 1.0
7 56 1.0
49 57 2.0
41 57 2.0
33 57 2.0
25 57 2.0
17 57 2.0
9 57 2.0
1 57 2.0
56 57 2.0
48 57 1.0
50 57 1.0
43 57 1.0
36 57 1.0
29 57 1.0
22 57 1.0
15 57 1.0
50 58 2.0
42 58 2.0
34 58 2.0
26 58 2.0
18 58 2.0
10 58 2.0
2 58 2.0
57 58 2.0
56 58 2.0
49 58 1.0
40 58 1.0
51 58 1.0
44 58 1.0
37 58 1.0
30 58 1.0
23 58 1.0
51 59 2.0
43 59 2.0
35 59 2.0
27 59 2.0
19 59 2.0
11 59 2.0
3 59 2.0
58 59 2.0
57 59 2.0
56 59 2.0
50 59 1.0
41 59 1.0
32 59 1.0
52 59 1.0
45 59 1.0
38 59 1.0
31 59 1.0
52 60 2.0
44 60 2.0
36 60 2.0
28 60 2.0
20 60 2.0
12 60 2.0
4 60 2.0
59 60 2.0
58 60 2.0
57 60 2.0
56 60 2.0
51 60 1.0
42 60 1.0
33 60 1.0
24 60 1.0
53 60 1.0
46 60 1.0
39 60 1.0
53 61 2.0
45 61 2.0
37 61 2.0
29 61 2.0
21 61 2.0
13 61 2.0
5 61 2.0
60 61 2.0
59 61 2.0
58 61 2.0
57 61 2.0
56 61 2.0
52 61 1.0
43 61 1.0
34 61 1.0
25 61 1.0
16 61 1.0
54 61 1.0
47 61 1.0
54 62 2.0
46 62 2.0
38 62 2.0
30 62 2.0
22 62 2.0
14 62 2.0
6 62 2.0
61 62 2.0
60 62 2.0
59 62 2.0
58 62 2.0
57 62 2.0
56 62 2.0
53 62 1.0
44 62 1.0
35 62 1.0
26 62 1.0
17 62 1.0
8 62 1.0
55 62 1.0
55 63 2.0
47 63 2.0
39 63 2.0
31 63 2.0
23 63 2.0
15 63 2.0
7 63 2.0
62 63 2.0
61 63 2.0
60 63 2.0
59 63 2.0
58 63 2.0
57 63 2.0
56 63 2.0
54 63 1.0
45 63 1.0
36 63 1.0
27 63 1.0
18 63 1.0
9 63 1.0
0 63 1.0
計算結果
qbsolvを実行する。-iで、作成したQUBOファイルを指定する。下記例では、qbsolv実行ファイルとQUBOファイル（input.qubo）をカレントディレクトリに置いたと仮定している。
$ ./qbsolv -i ./input.qubo
64 bits, find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
0000010000100000000010000000001010000000000100000100000000000001
-8.00000 Energy of solution
50 Number of Partitioned calls, 1 output sample
0.44003 seconds of classic cpu time
0と1で構成された列0000010000100000000010000000001010000000000100000100000000000001がqbsolvの計算結果である。QUBO変数とチェス盤のマスを1対1に対応させているので、上記結果を8×8で表現すると以下のようになる。
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
1が設定されているマスについては、上下左右斜め８方向すべて０になっていることが確認できる。
補足
エイト・クイーン問題では、1つの正解パターンを求めるだけではなく、全正解パターンを求めたいという要求もある。その場合には、-rオプションを指定して乱数種を変更しながら複数回試行する必要がある。また、特定のマスにクイーンを固定して配置し、その場合に得られるパターンを探索することも考えられる。特定のマスの配置を固定する場合には、対応するマスのパラメータを変更することで対応できる。$i = I$、$j = J$のマスに必ずクイーンを置くケースをモデル化すると、$q_{8I + J}$が1になりやすいようにハミルトニアンを再構築できる。
-2 \sum _{i} \sum _{j} q_{8i+j} \rightarrow -2 \sum _{i} \sum _{j} h_{8i+j} q_{8i+j}, \quad h_{k} = \left\{
\begin{array}{c}
1, & k \neq 8I + J\\
h, & k = 8I + J
\end{array}
\right. , \quad h > 1
まとめ
エイト・クイーン問題をイジングモデルのハミルトニアンでモデル化し、qbsolvを用いて実際に解き正しい答えが得られることを確認した。