N-Queens 問題

8-Queens 問題は、どの2つのクイーンも互いに攻撃し合わないように、チェス盤上に8つのクイーンを配置することを目的とします。つまり、同じ行、同じ列、同じ対角線（どちらの方向も）を共有するクイーンがあってはなりません。 N-Queens 問題はこれを一般化したもので、同じ条件のもとで $N\times N$ のチェス盤上に $N$ 個のクイーンを配置します。

QUBO++ を用いてこの問題を定式化するために、$N\times N$ のバイナリ変数行列 $X=(x_{i,j})$ を使用します。 $x_{i,j}=1$ は行 $i$、列 $j$ にクイーンが配置されていることを表し、$x_{i,j}=0$ はそうでないことを表します。 以下の制約を課します：

• 各行にちょうど1つのクイーン：

\[\begin{aligned} \sum_{j=0}^{N-1} x_{i,j}&=1 && (0\leq i\leq N-1) \end{aligned}\]

• 各列にちょうど1つのクイーン：

\[\begin{aligned} \sum_{i=0}^{N-1} x_{i,j}&=1 && (0\leq j\leq N-1) \end{aligned}\]

• 各対角線（右上から左下）に最大1つのクイーン： 対角線は $i+j=k$ で特徴づけられます。 長さ2以上の対角線のみを考慮し、つまり $k=1,2,\ldots,2N−3$ について以下を要求します：

\[\begin{aligned} 0\leq \sum_{\substack{0\le i,j \le N-1\\ i+j=k}}x_{i,j}\leq 1 &&(1\leq k\leq 2N-3) \end{aligned}\]

• $X$ の各反対角線の和が 0 または 1： 反対角線は $j−i=d$ で特徴づけられます。 長さ2以上の反対角線のみを考慮し、つまり $d=−(N−2),\ldots,(N−2)$ について以下を要求します：

\[\begin{aligned} 0\leq \sum_{\substack{0\le i,j \le N-1\\ j-i=d}}x_{i,j}\leq 1 &&(-(N-2)\leq d\leq (N-2)) \end{aligned}\]

QUBO++ プログラム

以下の QUBO++ プログラムは、上記の制約を qbpp::cons() で宣言し、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::cons(qbpp::vector_sum(x, 0) == 1) +
           qbpp::cons(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::cons(a <= 1);
  f += qbpp::cons(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;
  }
  std::cout << "violated constraints = " << f.cons(sol) << std::endl;
}

n$\times$n のバイナリ変数行列 x を導入し、x[i][j] = 1 は行 i、列 j にクイーンが配置されていることを示します。 列方向の和は qbpp::vector_sum(x, 0) で計算され、n 個の式のベクトル（列ごとに1つ）を返します。 == 演算子を要素ごとに適用すると、各列の和が 1 に等しいという制約の配列が生成され、qbpp::cons() はそれらをまとめて制約として宣言します。 同様に、qbpp::vector_sum(x, 1) を使って行方向のワンホット制約を宣言します。

対角線制約を強制するために、それぞれ長さ m = 2*n - 3 の2つの式ベクトル a と b を構築します。 各インデックス i について、a[i] は r + c の値が固定された対角線（右上から左下）上の変数を累積し、長さ 1 の対角線は除外します。 同様に、b[i] は c - r の値が固定された反対角線（左上から右下）上の変数を累積し、こちらも長さ 1 の対角線は除外します。 比較 a <= 1（b についても同様）は要素ごとに適用され、各対角線/反対角線に含まれるクイーンが最大1つという制約の配列を生成します。 これらを qbpp::cons() で宣言して f に加算します。

f.simplify_as_binary() で式を整理した後、Easy Solver が目標エネルギー 0 の解を探索します。 制約を宣言した式では、エネルギーが目標以下で、かつすべての制約が満たされたときに探索が止まります。 得られた割り当て sol は 8x8 のボードとして出力され、Q はクイーン、. は空きマスを表します。 最後に、破った制約の本数 f.cons(sol) を出力します。 例えば、プログラムは以下のような出力を生成する場合があります：

......Q.
.Q......
.....Q..
..Q.....
Q.......
...Q....
.......Q
....Q...
violated constraints = 0

この出力は、どの2つのクイーンも同じ行、列、対角線、反対角線を共有していないため、8つのクイーンの有効な配置であることを確認できます。