N-Queens 問題¶
8-Queens 問題は,どの2つのクイーンも互いに攻撃し合わないように,チェス盤上に8つのクイーンを配置することを目的とします.つまり,同じ行,同じ列,同じ対角線（どちらの方向も）を共有するクイーンがあってはなりません. N-Queens 問題はこれを一般化したもので,同じ条件のもとで \(N\times N\) のチェス盤上に \(N\) 個のクイーンを配置します.
Hi-QUBO を用いてこの問題を定式化するために,\(N\times N\) のバイナリ変数行列 \(X=(x_{i,j})\) を使用します. \(x_{i,j}=1\) は行 \(i\),列 \(j\) にクイーンが配置されていることを表し,\(x_{i,j}=0\) はそうでないことを表します. 以下の制約を課します：
各行にちょうど1つのクイーン：
各列にちょうど1つのクイーン：
各対角線（左上から右下）に最大1つのクイーン： 対角線は \(i+j=k\) で特徴づけられます. 長さ2以上の対角線のみを考慮し,つまり \(k=1,2,\ldots,2N−3\) について以下を要求します：
\(X\) の各反対角線の和が 0 または 1： 反対角線は \(j−i=d\) で特徴づけられます. 長さ2以上の反対角線のみを考慮し,つまり \(d=−(N−2),\ldots,(N−2)\) について以下を要求します：
Hi-QUBO プログラム
以下の Hi-QUBO プログラムは,上記の制約を表す式を構築し,Easy Solver を用いて実行可能解を求めます：
#include <qbpp/qbpp.hpp>
#include <qbpp/easy_solver.hpp>
int main() {
const int n = 8;
auto x = qbpp::var("x", n, n);
auto f = qbpp::sum(qbpp::vector_sum(x, 0) == 1) +
qbpp::sum(qbpp::vector_sum(x, 1) == 1);
const int m = 2 * n - 3;
auto a = qbpp::expr(m);
auto b = qbpp::expr(m);
for (int i = 0; i < m; ++i) {
const int k = i + 1;
for (int r = 0; r < n; ++r) {
const int c = k - r;
if (0 <= c && c < n) {
a[static_cast<size_t>(i)] +=
x[static_cast<size_t>(r)][static_cast<size_t>(c)];
}
}
const int d = i - (n - 2);
for (int r = 0; r < n; ++r) {
const int c = r + d;
if (0 <= c && c < n) {
b[static_cast<size_t>(i)] +=
x[static_cast<size_t>(r)][static_cast<size_t>(c)];
}
}
}
f += qbpp::sum(0 <= a <= 1);
f += qbpp::sum(0 <= b <= 1);
f.simplify_as_binary();
auto solver = qbpp::EasySolver(f);
auto sol = solver.search({{"target_energy", 0}});
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < n; j++) {
std::cout << (sol(x[i][j]) ? "Q" : ".");
}
std::cout << std::endl;
}
}
n\(\times\)n のバイナリ変数行列 x を導入し,x[i][j] = 1 は行 i,列 j にクイーンが配置されていることを示します.
列方向の和は qbpp::vector_sum(x, 0) で計算され,n 個の式のベクトル（列ごとに1つ）を返します.
== 演算子を要素ごとに適用すると,ペナルティ式のベクトルが生成されます.各式は,対応する列の和が 1 に等しい場合にのみ 0 になります.
同様に,qbpp::vector_sum(x, 1) を使って行方向のワンホット制約を強制できます.
対角線制約を強制するために,それぞれ長さ m = 2*n - 3 の2つの式ベクトル a と b を構築します.
各インデックス i について,a[i] は r + c の値が固定された対角線（左上から右下）上の変数を累積し,長さ 1 の対角線は除外します.
同様に,b[i] は c - r の値が固定された反対角線（右上から左下）上の変数を累積し,こちらも長さ 1 の対角線は除外します.
連鎖範囲比較 0 <= a <= 1（b についても同様）は要素ごとに適用され,各対角線/反対角線に最大1つのクイーンが含まれる場合にのみ 0 になるペナルティを生成します.
これらのペナルティが f に加算されます.
f.simplify_as_binary() で式をバイナリ QUBO 形式に変換した後,Easy Solver が目標エネルギー 0 の解を探索します.
得られた割り当て sol は 8x8 のボードとして出力され,Q はクイーン,. は空きマスを表します.
例えば,プログラムは以下のような出力を生成する場合があります：
この出力は,どの2つのクイーンも同じ行,列,対角線,反対角線を共有していないため,8つのクイーンの有効な配置であることを確認できます.
8-Queens 問題は,チェス盤上に8つのクイーンを,互いに攻撃し合わないように配置する問題です.すなわち,同じ行,同じ列,同じ対角線（どちらの方向も）を共有するクイーンが存在しないようにします. N-Queens 問題はこれを一般化したもので,\(N\times N\) のチェス盤上に同じ条件のもとで \(N\) 個のクイーンを配置します.
この問題を PyQBPP で定式化するために,\(N\times N\) のバイナリ変数の行列 \(X=(x_{i,j})\) を用います.ここで,\(x_{i,j}=1\) は行 \(i\),列 \(j\) にクイーンが配置されていることを表し,\(x_{i,j}=0\) はそうでないことを表します. 以下の制約を課します：
各行にちょうど1つのクイーン：
各列にちょうど1つのクイーン：
各対角線（左上から右下）に最大1つのクイーン： 対角線は \(i+j=k\) で特徴づけられます. 長さ2以上の対角線のみを考え,すなわち \(k=1,2,\ldots,2N−3\) に対して以下を要求します：
\(X\) の各反対角線の和が0または1： 反対角線は \(j−i=d\) で特徴づけられます. 長さ2以上の反対角線のみを考え,すなわち \(d=−(N−2),\ldots,(N−2)\) に対して以下を要求します：
PyQBPP プログラム
以下の PyQBPP プログラムは,上記の制約を表す式を構築し,Easy Solver を用いて実行可能解を求めます：
import pyqbpp as qbpp
n = 8
x = qbpp.var("x", shape=(n, n))
f = qbpp.sum(qbpp.vector_sum(x, axis=0) == 1) + \
qbpp.sum(qbpp.vector_sum(x, axis=1) == 1)
m = 2 * n - 3
a = qbpp.expr(shape=m)
b = qbpp.expr(shape=m)
for i in range(m):
k = i + 1
for r in range(n):
c = k - r
if 0 <= c < n:
a[i] += x[r][c]
d = i - (n - 2)
for r in range(n):
c = r + d
if 0 <= c < n:
b[i] += x[r][c]
f += qbpp.sum((0 <= a) & (qbpp.same <= 1))
f += qbpp.sum((0 <= b) & (qbpp.same <= 1))
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(target_energy=0)
for i in range(n):
for j in range(n):
print("Q" if sol(x[i][j]) == 1 else ".", end="")
print()
n\(\times\)n のバイナリ変数の行列 x を導入し,x[i][j] = 1 は行 i,列 j にクイーンが配置されていることを示します.
列方向の和は qbpp.vector_sum(x, axis=0) を用いて計算され,n 個の式のベクトル（各列に1つ）を返します.
... == 1 を要素ごとに適用すると,ペナルティ式のベクトルが生成されます.各式は,対応する列の和が1に等しい場合にのみ0と評価されます.
同様に,qbpp.vector_sum(x, axis=1) を用いて行方向の one-hot 制約を課すことができます.
ペナルティ式のベクトルを qbpp.sum(...) で包むことで,各ベクトルは単一のスカラー式に集約され,f に組み込まれます.
対角線制約を課すために,長さ m = 2*n - 3 の2つの式ベクトル a と b を qbpp.expr(shape=m) を用いて構築します.qbpp.expr(shape=m) はゼロ式からなる1次元配列を生成します.
各インデックス i について,a[i] は r + c の値が固定された対角線（左上から右下）上の変数を累積します（長さ1の対角線は除外）.
同様に,b[i] は c - r の値が固定された反対角線（右上から左下）上の変数を累積します（長さ1の対角線は除外）.
要素ごとの範囲制約 (0 <= a) & (qbpp.same <= 1)（b も同様）は,各対角線/反対角線に最大1つのクイーンが含まれる場合にのみ0となるペナルティ式のベクトルを生成します.
これらのペナルティは qbpp.sum(...) で集約され,f に加算されます.
インプレース呼び出し f.simplify_as_binary() で式をバイナリ QUBO 形式に変換した後,search() にキーワード引数 target_energy=0 を渡して Easy Solver が目標エネルギー 0 の解を探索します.
返されるオブジェクト sol は呼び出し構文 sol(x[i][j]) をサポートし,バイナリ変数 x[i][j] に割り当てられた値（0 または 1）を返します.
得られた割り当て sol は 8x8 の盤面として出力され,Q はクイーン,. は空のマスを表します.
sol(x[i][j]) は整数値を返すため,1 と比較して Q または . を出力するかを判定します.
例えば,プログラムは以下のような出力を生成する場合があります：
..Q.....
.....Q..
.......Q
.Q......
...Q....
Q.......
......Q.
....Q...
この出力は,同じ行,列,対角線,反対角線を共有するクイーンが存在しないため,8つのクイーンの有効な配置であることを確認しています.