3桁の算数問題

次の数学問題をQUBO++を使って解いてみましょう。

数学問題 各桁の積が252となる3桁の奇数をすべて求めよ。

整数の百の位、十の位、一の位をそれぞれ $x$、$y$、$z$ とします。 具体的には：

• $x$ は $[1, 9]$ の整数、
• $y$ は $[0, 9]$ の整数、
• $t$ は $[0, 4]$ の整数、
• $z = 2t + 1$ （したがって $z$ は奇数である）。

すると、3桁の整数 $xyz$ の値 $v$ は

次の条件を満たすすべての解を求める：

QUBO++プログラム

以下のQUBO++プログラムは全ての解を求める：

#include <set>

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  auto x = 1 <= qbpp::var_int("x") <= 9;
  auto y = 0 <= qbpp::var_int("y") <= 9;
  auto t = 0 <= qbpp::var_int("t") <= 4;
  auto z = 2 * t + 1;
  auto v = x * 100 + y * 10 + z;

  auto f = x * y * z == 252;

  f.simplify_as_binary();
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  std::set<int> s;
  for (const auto& sol : sols) {
    s.insert(static_cast<int>(sol(v)));
  }
  for (auto v : s) {
    std::cout << v << " ";
  }
  std::cout << std::endl;
}

このプログラムでは、 x, y, および t は上記の範囲を持つ整数変数として定義されます。 次に z, v、および f は式として定義されます。 Exhaustive Solverのインスタンスを作成し f を作成し、すべての最適解を sols.

なぜなら x, y, および t 複数の二進変数で符号化されるため、異なる二進値の割り当てが同じ整数値を表す可能性がある。 結果として、同じ桁の3つ組（x,y,z）が solsに複数回出現する可能性がある。 したがって、我々は std::set<int> という名前の s を呼び出し、結果として得られる整数値のみを収集することで重複を除去する。 v.

の整数値のみを収集することで重複を除去するという名前のを使用する。 s は以下のように出力される:

479 497 667 749 947