SequenceScore

Declared in astar/SequenceScore.h; the same class on the site of Doxygen.

template<int W, int H>
class SequenceScore

the sliding-tile puzzle with the sequence score heuristic of Nilsson

The heuristic is h = M + W S, M being the Manhattan distance and S the sequence score: on the 3 x 3 board S counts 1 if the centre does not hold its goal tile and 2 for each tile of the border not followed, clockwise, by the tile that follows it in the goal; on the other boards S counts 1 if the first cell does not hold its goal tile and 2 for each tile not followed, in row-major order, by the tile that follows it in the goal (Nilsson, “Problem-solving methods in artificial intelligence”, 1971). The heuristic is not admissible: A* finds a solution expanding fewer nodes, but not necessarily an optimal one.

Public Types

using Base = SlidingTile<W, H>

the puzzle

using state_type = typename Base::state_type

a packed board

using cost_type = typename Base::cost_type

the cost type

using board_type = typename Base::board_type

a board

Public Functions

inline explicit SequenceScore(const board_type &start, const board_type &goal = Base::korf_goal())

constructor, taking the start and the goal boards

inline state_type initial_state(void) const noexcept

inline bool is_goal(state_type s) const noexcept

inline std::uint64_t hash(state_type s) const noexcept

inline cost_type heuristic(state_type s) const noexcept

M + W S.

template<class F>
inline void for_each_successor(state_type s, cost_type, F &&f) const

inline const Base &base(void) const noexcept

the underlying puzzle

Public Static Attributes

static constexpr int cells = Base::cells

the cells