Nクイーンズ問題
8クイーン問題は、チェス盤上に8つのクイーンを配置し、互いに攻撃し合わないようにすることを目的とします。つまり、どのクイーンも同一の行、同一の列、または同一の対角線（いずれの方向でも）を共有しないようにします。 Nクイーン問題はこれを一般化したもので、同じ条件下で$N$個のクイーンを$N\times N$のチェス盤上に配置します。
この問題を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)$とし、以下の条件を満たすことを要求する：
QUBO++プログラム
以下のQUBO++プログラムは、上記の制約を表す式を構築し、Easy Solverを用いて解可能な解を見つける：
#include "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) == 1);
f += qbpp::sum(qbpp::vector_sum(qbpp::transpose(x)) == 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::easy_solver::EasySolver(f);
solver.target_energy(0);
auto sol = solver.search();
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;
}
}
An n$\times$n 行列 x が導入され、ここで x[i]\[j] = 1 はクイーンが行 i と列 jに配置されたことを示す。
行ごとの和は qbpp::vector_sum(x)によって計算され、各行に対応する n 式（各行ごとに1つ）のベクトルを返す。
演算子 == は要素ごとに適用され、ペナルティ式からなるベクトルを生成する。各式は、対応する行の和が1に等しい場合にのみ0となる。
最後に、 qbpp::sum() これらのペナルティを単一の式に集約し、各行にクイーンが正確に1つ含まれる場合にのみ最小値0を達成する。
列制約は同様に構築され、 qbpp::transpose(x).
対角線制約を強制するため、長さ m = 2*n - 3を持つ。
各インデックス i, a[i] は対角線上の変数を固定値 r + c （左上から右下への対角線）に固定値
を付与した変数を蓄積する（長さ1の対角線を除く）。
同様に、 b[i] は対角線上に変数を蓄積し、固定値 c - r （右上から左下への対角線）に固定値 0 <= a <= 1 （bについても同様）は要素ごとに適用され、各対角線/対角線上にクイーンが最大1つしか存在しない場合にのみペナルティが0となる。
これらのペナルティは f.
式を二値QUBO形式に変換した後 f.simplify_as_binary()で二項QUBO形式に変換した後、Easy Solverは目標エネルギー0の解を検索する。
結果として得られる割り当てsolは8×8の盤面として出力され、 Q はクイーンを、 . は空欄を示す。
例えば、プログラムは以下の出力を生成する可能性がある:
..Q.....
.....Q..
.......Q
.Q......
...Q....
Q.......
......Q.
....Q...
この出力は8つのクイーンの有効な配置を確認する。なぜなら、どのクイーンも同一の行、列、対角線、または対角線上に存在しないからである。