qbpp_nqueen.hpp

Go to the documentation of this file.

 
 
#ifndef QBPP_NQUEEN_HPP
#define QBPP_NQUEEN_HPP
 
#include "qbpp.hpp"
 
namespace qbpp {
namespace nqueen {
 
class NQueenQuadModel : public qbpp::QuadModel {
public:
  enum class Mode { EXPAND, FAST, PARALLEL };
 
private:
  const int dim_;
  const Vector<Vector<qbpp::Var>> X_;
 
  static qbpp::QuadModel expand_mode(int dim,
                                     const Vector<Vector<qbpp::Var>> &X) {
    // Create arrays of expressions to store the sums of the diagonals.
 
    auto a = qbpp::expr(2 * dim - 3);
    auto b = qbpp::expr(2 * dim - 3);
    for (int i = 0; i < 2 * dim - 3; i++) {
      int k = i + 1;
      for (int j = 0; j < dim; j++) {
        if (k - j >= 0 && k - j < dim) {
          a[i] += X[j][k - j];
        }
      }
      int l = dim - i - 1;
      for (int j = 0; j < dim; j++) {
        if (l + j >= 0 && l + j < dim) {
          b[i] += X[j][l + j];
        }
      }
    }
 
    auto expr = qbpp::sum((qbpp::vector_sum(X) == 1) +
                          (qbpp::vector_sum(qbpp::transpose(X)) == 1)) +
                qbpp::sum((0 <= a <= 1) + (0 <= b <= 1));
    expr.simplify_as_binary();
 
    return qbpp::QuadModel(expr);
  }
 
  static qbpp::QuadModel fast_mode(int dim,
                                   const Vector<Vector<qbpp::Var>> &X) {
    qbpp::Expr expr = dim;
    for (int x = 0; x < dim; ++x) {
      for (int y = 0; y < dim; ++y) {
        // Reward for placing a queen
        expr -= X[x][y];
        for (int i = x + 1; i < dim; ++i) {
          // Penalty for placing two queens in the same row
          expr += X[x][y] * X[i][y];
        }
        for (int j = y + 1; j < dim; ++j) {
          // Penalty for placing two queens in the same column
          expr += X[x][y] * X[x][j];
        }
        for (int d = 1; d < dim - x; ++d) {
          if (y - d >= 0) {
            // Penalty for placing two queens on the same anti-diagonal
            expr += X[x][y] * X[x + d][y - d];
          }
          if (y + d < dim) {
            // Penalty for placing two queens on the same diagonal
            expr += X[x][y] * X[x + d][y + d];
          }
        }
      }
    }
    return qbpp::QuadModel(expr.simplify_as_binary());
  }
 
  static qbpp::QuadModel parallel_mode(int dim,
                                       const Vector<Vector<qbpp::Var>> &X) {
    qbpp::Vector<qbpp::Expr> exprs(dim);
    tbb::parallel_for(0, dim, [&](int x) {
      for (int y = 0; y < dim; ++y) {
        // Reward for placing a queen
        exprs[x] -= X[x][y];
        for (int i = x + 1; i < dim; ++i) {
          // Penalty for placing two queens in the same row
          exprs[x] += X[x][y] * X[i][y];
        }
        for (int j = y + 1; j < dim; ++j) {
          // Penalty for placing two queens in the same column
          exprs[x] += X[x][y] * X[x][j];
        }
        for (int d = 1; d < dim - x; ++d) {
          if (y - d >= 0) {
            // Penalty for placing two queens on the same anti-diagonal
            exprs[x] += X[x][y] * X[x + d][y - d];
          }
          if (y + d < dim) {
            // Penalty for placing two queens on the same diagonal
            exprs[x] += X[x][y] * X[x + d][y + d];
          }
        }
      }
    });
 
    return qbpp::QuadModel(simplify_as_binary(qbpp::sum(exprs) + dim));
  }
 
  std::tuple<qbpp::QuadModel, int, Vector<Vector<qbpp::Var>>>
  helper_func(int dim, Mode mode) {
    Vector<Vector<qbpp::Var>> X(qbpp::var("X", dim, dim));
    switch (mode) {
    case Mode::EXPAND:
      return {expand_mode(dim, X), dim, X};
    case Mode::FAST:
      return {fast_mode(dim, X), dim, X};
    case Mode::PARALLEL:
      return {parallel_mode(dim, X), dim, X};
    default:
      throw std::runtime_error("Invalid mode");
    }
  }
 
  NQueenQuadModel(
      std::tuple<qbpp::QuadModel, int, Vector<Vector<qbpp::Var>>> &&tuple)
      : qbpp::QuadModel(std::get<0>(tuple)), dim_(std::get<1>(tuple)),
        X_(std::get<2>(tuple)) {}
 
public:
  NQueenQuadModel(int dim, Mode mode)
      : NQueenQuadModel(helper_func(dim, mode)) {}
 
  qbpp::Var get_var(int i, int j) const { return X_[i][j]; }
};
} // namespace nqueen
} // namespace qbpp
 
#endif // QBPP_NQUEEN_HPP