NQueens
Declared in astar/NQueens.h; the same class on the site of Doxygen.
-
class NQueens
the n-queens problem, with at most 32 queens
A queen is added in the leftmost empty column, in a row where no queen already on the board attacks it; a state is the number \( k \) of the queens on the board and the row of the queen of each column \( c < k \), the other rows being 0, with \( n \leq 32 \). Each queen costs 1, and the heuristic, the number of the empty columns, is exact on the states that lead to a solution: every state has \( f = n \), and A* with the ties broken in favour of the larger g behaves as a depth-first search.
The feature \( c n + r \) of Zobrist hashing is the queen of the column \( c \) in the row \( r \), for \( c < k \); the states do not fit a 64-bit word for \( n > 12 \), and the Domain gives no perfect hash.
Public Functions
-
inline explicit NQueens(int n)
constructor of the problem with \( n \) queens, \( 1 \leq n \leq 32 \)
-
template<class F>
inline void for_each_successor(const Board &s, int h, F &&f) const calls f( t , 1 , h - 1 ) for each row of the column \( k \) free of attacks
-
inline std::size_t num_features(void) const noexcept
the number of features: one per pair ( column , row )
-
template<class F>
inline void for_each_feature(const Board &s, F &&f) const calls f( c n + r ) for the queen of each column \( c < k \), in the row \( r \)
-
inline int size(void) const noexcept
the size of the board
-
struct Board
a board: the queens placed and the row of each of them
-
inline explicit NQueens(int n)