Class to generate a QUBO model for the N-Queens problem. More...

#include <qbpp_nqueen.hpp>

Inheritance diagram for qbpp::nqueen::NQueenQuadModel:

Collaboration diagram for qbpp::nqueen::NQueenQuadModel:

[legend]

Public Types
enum class	Mode { EXPAND , FAST , PARALLEL }

Public Member Functions
	NQueenQuadModel (int dim, Mode mode)
	Constructor: Creates an N-Queens QUBO expression. More...

qbpp::Var	get_var (int i, int j) const
	Gets the variable at (i, j) More...

const std::vector< coeff_t > &	get_linear () const

coeff_t	get_linear (vindex_t index) const

const std::vector< vindex_t > &	get_degree () const

vindex_t	get_degree (vindex_t index) const

const std::vector< std::vector< std::pair< vindex_t, coeff_t > > > &	get_quadratic () const

std::pair< vindex_t, coeff_t >	get_quadratic (vindex_t i, vindex_t j) const

size_t	term_count (vindex_t deg) const

size_t	term_count () const override

coeff_t	get_min_coeff () const

coeff_t	get_max_coeff () const

vindex_t	var_count () const

Var	get_var (vindex_t index) const

vindex_t	get_index (Var var) const

bool	has (Var var) const

const Expr &	get_expr () const

	operator const Expr & () const

energy_t	get_constant () const

const Terms &	get_terms () const

std::vector< Var >	get_index_var () const

Static Protected Member Functions
static const Expr &	check_expr (const Expr &expr)

static Expr	check_expr (Expr &&expr)

Protected Attributes
const std::shared_ptr< const Expr >	expr_ptr_

const std::shared_ptr< const impl::IndexVarMapper >	index_var_ptr_

Private Member Functions
std::tuple< qbpp::QuadModel, int, Vector< Vector< qbpp::Var > > >	helper_func (int dim, Mode mode)
	Helper function to compute initial values for member variables. More...

	NQueenQuadModel (std::tuple< qbpp::QuadModel, int, Vector< Vector< qbpp::Var >>> &&tuple)
	Constructor to initialize member variables. More...

Static Private Member Functions
static qbpp::QuadModel	expand_mode (int dim, const Vector< Vector< qbpp::Var >> &X)
	Generates qbpp::Expr for the N-Queens problem. More...

static qbpp::QuadModel	fast_mode (int dim, const Vector< Vector< qbpp::Var >> &X)
	Generates the QUBO expression for the N-Queens problem. More...

static qbpp::QuadModel	parallel_mode (int dim, const Vector< Vector< qbpp::Var >> &X)
	Generates the QUBO expression for the N-Queens problem using TBB in parallel. More...

Private Attributes
const int	dim_
	Dimension of the chessboard. More...

const Vector< Vector< qbpp::Var > >	X_
	2-dimensional vector of qbpp::Var representing the chessboard More...

const std::shared_ptr< const Impl >	pimpl_

const std::vector< coeff_t > &	linear_

const std::vector< vindex_t > &	degree_

const std::vector< std::vector< std::pair< vindex_t, coeff_t > > > &	quadratic_

Detailed Description

Class to generate a QUBO model for the N-Queens problem.

This class is a derived class of qbpp::QuadModel with the 2-dimensional vector of Var objects representing the chessboard.

Definition at line 22 of file qbpp_nqueen.hpp.

Member Enumeration Documentation

◆ Mode

enum qbpp::nqueen::NQueenQuadModel::Mode

strong

Enumerator
EXPAND
FAST
PARALLEL

Definition at line 24 of file qbpp_nqueen.hpp.

Constructor & Destructor Documentation

◆ NQueenQuadModel() [1/2]

qbpp::nqueen::NQueenQuadModel::NQueenQuadModel ( std::tuple< qbpp::QuadModel, int, Vector< Vector< qbpp::Var >>> && tuple )

inlineprivate

Constructor to initialize member variables.

Parameters

tuple A tuple containing values to initialize the member variables.

Note: Since the arguments are the return values of the helper function, the rvalue reference is used.

Definition at line 159 of file qbpp_nqueen.hpp.

◆ NQueenQuadModel() [2/2]

qbpp::nqueen::NQueenQuadModel::NQueenQuadModel	(	int	dim,
		Mode	mode
	)

inline

Constructor: Creates an N-Queens QUBO expression.

Parameters

dim	Dimension of the chessboard
mode	Mode to generate the QUBO expression

Definition at line 168 of file qbpp_nqueen.hpp.

Member Function Documentation

◆ expand_mode()

static qbpp::QuadModel qbpp::nqueen::NQueenQuadModel::expand_mode	(	int	dim,
		const Vector< Vector< qbpp::Var >> &	X
	)

inlinestaticprivate

Generates qbpp::Expr for the N-Queens problem.

Returns: qbpp::Expr for the N-Queens problem

The expression is created using the one-hot and zero-one-hot constraints. If all constraints are satisfied, board variables store correct placement of queens and the energy value is 0.

Definition at line 38 of file qbpp_nqueen.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fast_mode()

static qbpp::QuadModel qbpp::nqueen::NQueenQuadModel::fast_mode	(	int	dim,
		const Vector< Vector< qbpp::Var >> &	X
	)

inlinestaticprivate

Generates the QUBO expression for the N-Queens problem.

Returns: QUBO expression for the N-Queens problem

The expression is created by setting the penalty for placing two queens in the same row, column, and diagonal. If the placement of queens is correct, the value of the expression will be 0.

Definition at line 72 of file qbpp_nqueen.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ parallel_mode()

static qbpp::QuadModel qbpp::nqueen::NQueenQuadModel::parallel_mode	(	int	dim,
		const Vector< Vector< qbpp::Var >> &	X
	)

inlinestaticprivate

Generates the QUBO expression for the N-Queens problem using TBB in parallel.

Definition at line 104 of file qbpp_nqueen.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ helper_func()

std::tuple<qbpp::QuadModel, int, Vector<Vector<qbpp::Var> > > qbpp::nqueen::NQueenQuadModel::helper_func	(	int	dim,
		Mode	mode
	)

inlineprivate

Helper function to compute initial values for member variables.

Parameters

dim	The dimension of the chessboard.
mode	The mode to generate the QUBO expression.

Returns: A tuple containing the QUBO model, dimension, and variables.

Definition at line 140 of file qbpp_nqueen.hpp.

Here is the call graph for this function:

◆ get_var() [1/2]

qbpp::Var qbpp::nqueen::NQueenQuadModel::get_var	(	int	i,
		int	j
	)		const

inline

Gets the variable at (i, j)

Parameters

i	Row index
j	Column index

Returns: Var object at (i, j)

Definition at line 175 of file qbpp_nqueen.hpp.

Here is the caller graph for this function:

◆ get_linear() [1/2]

const std::vector<coeff_t>& qbpp::QuadModel::get_linear ( ) const

inlineinherited

Definition at line 1241 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_linear() [2/2]

coeff_t qbpp::QuadModel::get_linear ( vindex_t index ) const

inlineinherited

Definition at line 1250 of file qbpp.hpp.

◆ get_degree() [1/2]

const std::vector<vindex_t>& qbpp::QuadModel::get_degree ( ) const

inlineinherited

Definition at line 1243 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_degree() [2/2]

vindex_t qbpp::QuadModel::get_degree ( vindex_t index ) const

inlineinherited

Definition at line 1252 of file qbpp.hpp.

◆ get_quadratic() [1/2]

const std::vector<std::vector<std::pair<vindex_t, coeff_t> > >& qbpp::QuadModel::get_quadratic ( ) const

inlineinherited

Definition at line 1245 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_quadratic() [2/2]

std::pair<vindex_t, coeff_t> qbpp::QuadModel::get_quadratic	(	vindex_t	i,
		vindex_t	j
	)		const

inlineinherited

Definition at line 1254 of file qbpp.hpp.

◆ term_count() [1/2]

size_t qbpp::QuadModel::term_count ( vindex_t deg ) const

inlineinherited

Definition at line 1258 of file qbpp.hpp.

Here is the caller graph for this function:

◆ term_count() [2/2]

size_t qbpp::QuadModel::term_count ( ) const

inlineoverridevirtualinherited

Reimplemented from qbpp::Model.

Definition at line 1268 of file qbpp.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_min_coeff()

coeff_t qbpp::QuadModel::get_min_coeff ( ) const

inlineinherited

Definition at line 1270 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_max_coeff()

coeff_t qbpp::QuadModel::get_max_coeff ( ) const

inlineinherited

Definition at line 1272 of file qbpp.hpp.

Here is the caller graph for this function:

◆ check_expr() [1/2]

static const Expr& qbpp::Model::check_expr ( const Expr & expr )

inlinestaticprotectedinherited

Definition at line 1111 of file qbpp.hpp.

Here is the call graph for this function:

◆ check_expr() [2/2]

static Expr qbpp::Model::check_expr ( Expr && expr )

inlinestaticprotectedinherited

Definition at line 1120 of file qbpp.hpp.

Here is the call graph for this function:

◆ var_count()

vindex_t qbpp::Model::var_count ( ) const

inlineinherited

Definition at line 1154 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_var() [2/2]

Var qbpp::Model::get_var ( vindex_t index ) const

inlineinherited

Definition at line 1156 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_index()

vindex_t qbpp::Model::get_index ( Var var ) const

inlineinherited

Definition at line 1158 of file qbpp.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ has()

bool qbpp::Model::has ( Var var ) const

inlineinherited

Definition at line 1160 of file qbpp.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_expr()

const Expr& qbpp::Model::get_expr ( ) const

inlineinherited

Definition at line 1164 of file qbpp.hpp.

Here is the caller graph for this function:

◆ operator const Expr &()

qbpp::Model::operator const Expr & ( ) const

inlineinherited

Definition at line 1166 of file qbpp.hpp.

◆ get_constant()

energy_t qbpp::Model::get_constant ( ) const

inlineinherited

Definition at line 1168 of file qbpp.hpp.

Here is the caller graph for this function:

◆ get_terms()

const Terms& qbpp::Model::get_terms ( ) const

inlineinherited

Definition at line 1170 of file qbpp.hpp.

◆ get_index_var()

std::vector<Var> qbpp::Model::get_index_var ( ) const

inlineinherited

Definition at line 1172 of file qbpp.hpp.

Here is the caller graph for this function:

Member Data Documentation

◆ dim_

const int qbpp::nqueen::NQueenQuadModel::dim_

private

Dimension of the chessboard.

Definition at line 28 of file qbpp_nqueen.hpp.

◆ X_

const Vector<Vector<qbpp::Var> > qbpp::nqueen::NQueenQuadModel::X_

private

2-dimensional vector of qbpp::Var representing the chessboard

The Var object X_[i][j] is 1 if a queen is placed at (i, j) and 0

Definition at line 31 of file qbpp_nqueen.hpp.

◆ pimpl_

const std::shared_ptr<const Impl> qbpp::QuadModel::pimpl_

privateinherited

Definition at line 1195 of file qbpp.hpp.

◆ linear_

const std::vector<coeff_t>& qbpp::QuadModel::linear_

privateinherited

Definition at line 1197 of file qbpp.hpp.

◆ degree_

const std::vector<vindex_t>& qbpp::QuadModel::degree_

privateinherited

Definition at line 1199 of file qbpp.hpp.

◆ quadratic_

const std::vector<std::vector<std::pair<vindex_t, coeff_t> > >& qbpp::QuadModel::quadratic_

privateinherited

Definition at line 1201 of file qbpp.hpp.

◆ expr_ptr_

const std::shared_ptr<const Expr> qbpp::Model::expr_ptr_

protectedinherited

Definition at line 1107 of file qbpp.hpp.

◆ index_var_ptr_

const std::shared_ptr<const impl::IndexVarMapper> qbpp::Model::index_var_ptr_

protectedinherited

Definition at line 1109 of file qbpp.hpp.

The documentation for this class was generated from the following file:

sample/qbpp_nqueen.hpp

Public Types

Public Member Functions

Static Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ Mode

Constructor & Destructor Documentation

◆ NQueenQuadModel() [1/2]

◆ NQueenQuadModel() [2/2]

Member Function Documentation

◆ expand_mode()

◆ fast_mode()

◆ parallel_mode()

◆ helper_func()

◆ get_var() [1/2]

◆ get_linear() [1/2]

◆ get_linear() [2/2]

◆ get_degree() [1/2]

◆ get_degree() [2/2]

◆ get_quadratic() [1/2]

◆ get_quadratic() [2/2]

◆ term_count() [1/2]

◆ term_count() [2/2]

◆ get_min_coeff()

◆ get_max_coeff()

◆ check_expr() [1/2]

◆ check_expr() [2/2]

◆ var_count()

◆ get_var() [2/2]

◆ get_index()

◆ has()

◆ get_expr()

◆ operator const Expr &()

◆ get_constant()

◆ get_terms()

◆ get_index_var()

Member Data Documentation

◆ dim_

◆ X_

◆ pimpl_

◆ linear_

◆ degree_

◆ quadratic_

◆ expr_ptr_

◆ index_var_ptr_