ABS2 QUBO Solver
N-QueensパズルのQUBOをABS2 QUBO Solverを使って解きます．ABS2はGPUを用いたQUBOソルバーで，公開されているC++のAPIを呼び出し，QUBOモデルの設定とソルバーの実行を行います．N-QueensパズルをQUBO形式に変換するのに、以下に紹介した手法を採用します．
C++プログラム
ABS2::Modelクラスを継承したNQUEENS_Modelクラスを用いて，N-QueensパズルのQUBOモデルを定義しています．メンバ関数setを使って，QUBOモデルの係数を設定しています．また，ABS2::Paramクラスのインスタンスparamには，ABS2への入力パラメータとしてtime_limitとtarget_energyを指定しています。modelとparamをソルバーsolverに渡すことで、ABS2は解を計算し、その結果をsolに格納します。
#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