TilePattern< W, H > Class Template Reference

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

#include <PBeFS/astar/PatternDatabase.h>

Classes
struct	Moves
	the cells adjacent to a cell, in the order up, left, right, down More...

Public Types
using	board_type = std::array< std::uint8_t , cells >
	a board

Public Member Functions
	TilePattern (const std::vector< int > &tiles, const board_type &goal=korf_goal())
	constructor, taking the tiles of the pattern and the goal board
int	size (void) const noexcept
	the number k of the tiles of the pattern
const std::vector< int > &	tiles (void) const noexcept
	the tiles of the pattern
const board_type &	goal (void) const noexcept
	the goal board
int	goal_cell (int i) const noexcept
	the goal cell of the i-th tile of the pattern
std::uint64_t	entries (void) const noexcept
	the number of the placements, n! / ( n - k )!
std::uint64_t	goal_rank (void) const noexcept
	the rank of the goal placement
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
void	unrank (std::uint64_t r, std::uint8_t *p) const noexcept
	writes in p the placement of rank r < entries()
int	manhattan (const std::uint8_t *p) const noexcept
	the Manhattan distance of the tiles of the placement p from the goal

Static Public Member Functions
static board_type	korf_goal (void)
	the goal of Korf (1985): the blank in the first cell, then 1 , 2 , ...
static const Moves &	moves (int c) noexcept
	the cells adjacent to the cell c
static int	distance (int a, int b) noexcept
	the Manhattan distance between two cells
static 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 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)

Static Public Attributes
static constexpr int	cells = W * H
	the number of cells
static constexpr std::uint32_t	c_full
	the mask of all the cells

Detailed Description

template<int W, int H>
class PBeFS_di_unipi_it::TilePattern< W, H >

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.

Member Typedef Documentation

board_type

template<int W, int H>

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

a board

Constructor & Destructor Documentation

TilePattern()

template<int W, int H>

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

inlineexplicit

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.

Member Function Documentation

distance()

template<int W, int H>

int distance ( int a, int b )

inlinestaticnodiscardnoexcept

the Manhattan distance between two cells

entries()

template<int W, int H>

std::uint64_t entries ( void ) const

inlinenodiscardnoexcept

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

goal()

template<int W, int H>

const board_type & goal ( void ) const

inlinenodiscardnoexcept

the goal board

goal_cell()

template<int W, int H>

int goal_cell ( int i ) const

inlinenodiscardnoexcept

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

goal_rank()

template<int W, int H>

std::uint64_t goal_rank ( void ) const

inlinenodiscardnoexcept

the rank of the goal placement

korf_goal()

template<int W, int H>

board_type korf_goal ( void )

inlinestaticnodiscard

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

manhattan()

template<int W, int H>

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

inlinenodiscardnoexcept

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

moves()

template<int W, int H>

const Moves & moves ( int c )

inlinestaticnodiscardnoexcept

the cells adjacent to the cell c

rank()

template<int W, int H>

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

inlinenodiscardnoexcept

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

region()

template<int W, int H>

std::uint32_t region ( std::uint32_t free, int b )

inlinestaticnodiscardnoexcept

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)

select()

template<int W, int H>

int select ( std::uint32_t x, int j )

inlinestaticnodiscardnoexcept

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

size()

template<int W, int H>

int size ( void ) const

inlinenodiscardnoexcept

the number k of the tiles of the pattern

tiles()

template<int W, int H>

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

inlinenodiscardnoexcept

the tiles of the pattern

unrank()

template<int W, int H>

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

inlinenoexcept

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

Member Data Documentation

c_full

template<int W, int H>

std::uint32_t c_full

staticconstexpr

Initial value:

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

the mask of all the cells

cells

template<int W, int H>

int cells = W * H

staticconstexpr

the number of cells

---

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

• PBeFS/astar/PatternDatabase.h