TilePattern

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

template<int W, int H>
class TilePattern

a pattern of the sliding-tile puzzle and the ranking of its placements

The board has W x H cells, at most 32, the cell r W + k being in row r and column k as in SlidingTile. A placement of the k tiles of the pattern is the array of their cells, in the order of the tiles given to the constructor, and its rank is that of the k-permutation in lexicographic order: the digit \( d_i \) of the tile \( i \) is the number of the cells below \( p_i \) not held by the tiles before it, and the rank is \( \sum_i d_i \prod_{j > i} ( n - j ) \), which takes \( k \) population counts, the inverse \( k \) divisions and \( k \) selections of a bit. Two consecutive ranks differ only in the cell of the last tile, among the cells free of the others.

Public Types

using board_type = std::array<std::uint8_t, cells>

a board

Public Functions

inline explicit TilePattern(const std::vector<int> &tiles, const board_type &goal = korf_goal())

constructor, taking the tiles of the pattern and the goal board

Throws std::invalid_argument if tiles is empty, has a tile twice or a tile out of 1 , … , W H - 1, or if goal is not a permutation of the cells.

inline int size(void) const noexcept

the number k of the tiles of the pattern

inline const std::vector<int> &tiles(void) const noexcept

the tiles of the pattern

inline const board_type &goal(void) const noexcept

the goal board

inline int goal_cell(int i) const noexcept

the goal cell of the i-th tile of the pattern

inline std::uint64_t entries(void) const noexcept

the number of the placements, n! / ( n - k )!

inline std::uint64_t goal_rank(void) const noexcept

the rank of the goal placement

inline std::uint64_t rank(const std::uint8_t *p) const noexcept

the rank of the placement p, p[ i ] the cell of the i-th tile

inline void unrank(std::uint64_t r, std::uint8_t *p) const noexcept

writes in p the placement of rank r < entries()

inline int manhattan(const std::uint8_t *p) const noexcept

the Manhattan distance of the tiles of the placement p from the goal

Public Static Functions

static inline board_type korf_goal(void)

the goal of Korf (1985): the blank in the first cell, then 1 , 2 , …

static inline const Moves &moves(int c) noexcept

the cells adjacent to the cell c

static inline int distance(int a, int b) noexcept

the Manhattan distance between two cells

static inline int select(std::uint32_t x, int j) noexcept

the place of the j-th set bit of x (from 0), which must exist

static inline std::uint32_t region(std::uint32_t free, int b) noexcept

the cells that a blank in the cell b reaches through the cells of free, i.e., the region of b in the mask free (b in free)

Public Static Attributes

static constexpr int cells = W * H

the number of cells

static constexpr std::uint32_t c_full = cells == 32 ? ~std::uint32_t(0) : (std::uint32_t(1) << cells) - 1u

the mask of all the cells

struct Moves

the cells adjacent to a cell, in the order up, left, right, down

Public Members

int n = 0

their number

int cell[4] = {0, 0, 0, 0}

the cells