|
| | NQueens (int n) |
| | constructor of the problem with \( n \) queens, \( 1 \leq n \leq 32 \)
|
| Board | initial_state (void) const noexcept |
| bool | is_goal (const Board &s) const noexcept |
| std::uint64_t | hash (const Board &s) const noexcept |
| int | heuristic (const Board &s) const noexcept |
| template<class F> |
| 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
|
| std::size_t | num_features (void) const noexcept |
| | the number of features: one per pair ( column , row )
|
| template<class F> |
| 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 \)
|
| int | size (void) const noexcept |
| | the size of the board
|
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.
1.15.0