N-QueensパズルのQUBOをABS2 QUBO Solverで解く

# ABS2 QUBO Solver
N-QueensパズルのQUBOを[ABS2 QUBO Solver](https://abs2.cs.hiroshima-u.ac.jp/)を使って解きます．ABS2はGPUを用いたQUBOソルバーで，公開されているC++のAPIを呼び出し，QUBOモデルの設定とソルバーの実行を行います．N-QueensパズルをQUBO形式に変換するのに、以下に紹介した手法を採用します．
*  [N-QueensパズルのQUBOを高速生成し，Gurobiで解く](https://qiita.com/koji_nakano/items/d873a80dc577f00c898c)

# C++プログラム
`ABS2::Model`クラスを継承した`NQUEENS_Model`クラスを用いて，N-QueensパズルのQUBOモデルを定義しています．メンバ関数`set`を使って，QUBOモデルの係数を設定しています．また，`ABS2::Param`クラスのインスタンスparamには，ABS2への入力パラメータとして`time_limit`と`target_energy`を指定しています。`model`と`param`をソルバー`solver`に渡すことで、ABS2は解を計算し、その結果を`sol`に格納します。



```C++
#include "abs2.hpp"
#include <cstdlib>

// Class to model the QUBO formulation of the N-Queens problem.
class NQUEENS_Model : public ABS2::Model {
  // Dimension of the chessboard (dim x dim).
  const int dim;

  // Sets the value for the pair ((x1,y1),(x2,y2)) in the N-Queens QUBO model.
  void set(int x1, int y1, int x2, int y2, int val) {
    // Delegates to the set method of ABS2::Model with flattened indices.
    ABS2::Model::set(x1 * dim + y1, x2 * dim + y2, val);
  }

public:
  // Initializes a QUBO model for the N-Queens on a dim x dim chessboard.
  NQUEENS_Model(int dim) : ABS2::Model(dim * dim, 8), dim(dim) {
    for (int x = 0; x < dim; ++x) {
      for (int y = 0; y < dim; ++y) {
        set(x, y, x, y, -1); // Self-occupancy reward
        for (int i = x + 1; i < dim; ++i)
          set(x, y, i, y, +1); // Vertical conflict penalty
        for (int j = y + 1; j < dim; ++j)
          set(x, y, x, j, +1);              // Horizontal conflict penalty
        for (int d = 1; d < dim - x; ++d) { // Diagonal conflict penalties
          if (y - d >= 0)
            set(x, y, x + d, y - d, +1);
          if (y + d < dim)
            set(x, y, x + d, y + d, +1);
        }
      }
    }
  }
};

int main(int argc, char *argv[]) {
  // Default dimension for the N-Queens puzzle.
  int dim = 32;

  // Allows specifying the chessboard dimension via a command line argument.
  if (argc > 1) {
    dim = std::atoi(argv[1]);
  }

  // Initialize the ABS2 QUBO solver.
  ABS2::Solver solver;
  // Generate a QUBO model for the N-Queens problem on a dim x dim chessboard.
  NQUEENS_Model model(dim);
  // Create a parameters object to store solver parameters.
  ABS2::Param param;
  // Set a time limit of 60 seconds for the solver.
  param.set("time_limit", "60");
  // Set the target energy level to negative the board dimension.
  param.set("target_energy", std::to_string(-dim));
  // Solve the model with the specified parameters.
  auto sol = solver(model, param);
  // Print the solution matrix.
  for (int x = 0; x < dim; ++x) {
    for (int y = 0; y < dim; ++y)
      std::cout << sol.get(x * dim + y);
    std::cout << "\n";
  }
  // Print solution attributes.
  sol.print("attrs");
}
```

# 実行例
32-Queensパズルの最適解$-32$が得られています．
```
00000000000000000000100000000000
00000000000000000100000000000000
00000000000000000000000000100000
00000000000010000000000000000000
00000000000000000000000000010000
00000000000000000010000000000000
00001000000000000000000000000000
00100000000000000000000000000000
10000000000000000000000000000000
00000000100000000000000000000000
00000000000000000000000001000000
00000000000000100000000000000000
00000000000000000000000000000100
00000000000000000000000000000001
00000000001000000000000000000000
00000010000000000000000000000000
00010000000000000000000000000000
00000100000000000000000000000000
00000000000000000001000000000000
00000000000000000000000100000000
00000000010000000000000000000000
00000000000000000000000000001000
00000000000000001000000000000000
00000001000000000000000000000000
00000000000000000000000010000000
00000000000000000000000000000010
01000000000000000000000000000000
00000000000001000000000000000000
00000000000100000000000000000000
00000000000000000000001000000000
00000000000000010000000000000000
00000000000000000000010000000000
kernel_time=0.080316 runtime=0.090687 tts=0.020885 energy=-32 size=1024 solver=abs2
```

# 参考文献
* Koji Nakano, Daisuke Takafuji, Yasuaki Ito, Takashi Yazane, Junko Yano, Shiro Ozaki, Ryota Katsuki, Rie Mori: **Diverse Adaptive Bulk Search: a Framework for Solving QUBO Problems on Multiple GPUs**. IPDPS Workshops 2023: 314-325 ([DOI](https://doi.org/10.1109/IPDPSW59300.2023.00060),[arXiv](https://arxiv.org/abs/2207.03069))