SlidingTile< W, H > Class Template Reference

the sliding-tile puzzle on a board of at most 25 cells More...

#include <PBeFS/astar/SlidingTile.h>

Inheritance diagram for SlidingTile< W, H >:

Public Types
using	state_type
	a packed board
using	cost_type = int
	the cost type
using	board_type = std::array< std::uint8_t , cells >
	a board

Public Member Functions
	SlidingTile (const board_type &start, const board_type &goal=korf_goal())
	constructor, taking the start and the goal boards
state_type	initial_state (void) const noexcept
	the start board
bool	is_goal (state_type s) const noexcept
	true if s is the goal board
std::uint64_t	hash (state_type s) const noexcept
	the hash of a board: its packed integer, mixed
cost_type	heuristic (state_type s) const noexcept
	the Manhattan distance of s from the goal
template<class F>
void	for_each_successor (state_type s, cost_type h, F &&f) const
	calls f( t , 1 , h( t ) ) for each successor t of s
template<class F>
void	for_each_successor (state_type s, cost_type h, std::uint8_t op, F &&f) const
	as above, but without the successor that op, the cell where the blank was, leads back to; the operator of a successor is the cell of the blank in s
template<class F>
void	for_each_feature (state_type s, F &&f) const
	calls f( t W H + c ) for each tile t != 0 in each cell c of s
template<class F>
void	for_each_feature_change (state_type s, state_type t, F &&f) const
	calls f( k W H + c ) and f( k W H + b ) for the tile k that the move from s to its successor t slides from the cell c to the cell b of the blank of s
std::uint64_t	abstract_state (state_type s) const noexcept
	the abstract state of AHDA*: the cells of tiles 1, 2 and 3
std::size_t	nblock (state_type s) const noexcept
	the nblock of PBNF: the cells of the blank and of tiles 1 and 2
template<class F>
void	for_each_nblock_successor (std::size_t b, F &&f) const
	calls f( b' ) for each abstract successor b' of the nblock b
cost_type	pairwise_heuristic (state_type s, state_type t) const noexcept
	the heuristic of PA*SE: the sum of the displacements of the tiles
std::uint64_t	perfect_hash (state_type s) const noexcept
	the lexicographic rank of the permutation of the cells of the tiles

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 constexpr std::size_t	num_features (void) noexcept
	the number of features: one per pair ( tile , cell )
static constexpr std::size_t	num_abstract_features (void) noexcept
	the number of abstract features: one per pair ( tile , half board )
static constexpr std::size_t	abstract_feature (std::size_t i) noexcept
	the abstract feature of a feature: the tile and the half of its cell
static constexpr std::size_t	num_nblocks (void) noexcept
	the number of nblocks: one per triple of cells, not all of them used
static int	tile (state_type s, int c) noexcept
	the tile in the cell c of s
static int	blank (state_type s) noexcept
	the cell of the blank in s, i.e., of the zero field of the integer
static state_type	pack (const board_type &b) noexcept
	packs a board into a word
static board_type	unpack (state_type s) noexcept
	unpacks a word into a board
static board_type	parse (const std::string &text)
	reads a board: W H numbers, the tiles cell by cell, 0 for the blank
static void	print (std::ostream &os, state_type s)
	prints a board, one row per line

Static Public Attributes
static constexpr int	width = W
	the number of columns
static constexpr int	height = H
	the number of rows
static constexpr int	cells = W * H
	the number of cells
static constexpr int	bits = cells <= 16 ? 4 : 5
	the bits of a cell

Detailed Description

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

the sliding-tile puzzle on a board of at most 25 cells

The board has \( W \times H \) cells, with \( W H \leq 25 \). A state is packed into one integer, the field of \( b \) bits of the cell \( i = r W + k \) holding the tile in row \( r \) and column \( k \) (0 being the blank): a word of 64 bits with \( b = 4 \) up to 16 cells, as for the 15-puzzle, and a Word128 with \( b = 5 \) above, as for the 24-puzzle. The integer is at the same time the state, its equality test and the key of its hash, as advocated by Burns et al. (SoCS 2012). The blank is found as the zero field of the integer with a few bitwise operations, and the Manhattan distance is updated incrementally from a table of the change caused by each move of each tile.

The feature i of Zobrist hashing is "tile t is in cell c", with \( i = t W H + c \), for the tiles \( t = 1 , \ldots , W H - 1 \). The abstract feature of Abstract Zobrist hashing keeps of the cell only whether it lies in the upper or in the lower half of the board, which is the hand-crafted projection of Jinnai and Fukunaga (JAIR 2017, fig. 8b) for the 15-puzzle. The state abstraction of AHDA* looks at the cells of tiles 1, 2 and 3, and the nblocks of PBNF at those of the blank and of tiles 1 and 2 [see Burns et al., JAIR 2010]. The perfect hash, the rank of the permutation, is given only up to 20 cells, since 21! exceeds \( 2^{64} \).

Member Typedef Documentation

board_type

template<int W, int H>

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

a board

cost_type

template<int W, int H>

using cost_type = int

the cost type

state_type

template<int W, int H>

using state_type

Initial value:

 std::conditional_t< cells <= 16 , std::uint64_t ,
                                        Word128 >

a packed board

Constructor & Destructor Documentation

SlidingTile()

template<int W, int H>

SlidingTile ( const board_type & start, const board_type & goal = korf_goal() )

inlineexplicit

constructor, taking the start and the goal boards

Constructs the puzzle of going from start to goal; throws std::invalid_argument if either is not a permutation of 0 , ... , W H - 1, or if the goal cannot be reached from the start.

Member Function Documentation

abstract_feature()

template<int W, int H>

constexpr std::size_t abstract_feature ( std::size_t i )

inlinestaticnodiscardconstexprnoexcept

the abstract feature of a feature: the tile and the half of its cell

abstract_state()

template<int W, int H>

std::uint64_t abstract_state ( state_type s ) const

inlinenodiscardnoexcept

the abstract state of AHDA*: the cells of tiles 1, 2 and 3

blank()

template<int W, int H>

int blank ( state_type s )

inlinestaticnodiscardnoexcept

the cell of the blank in s, i.e., of the zero field of the integer

The bits of each field are or-ed into its lowest one, which is then 0 only in the field of the blank.

for_each_feature()

template<int W, int H>

template<class F>

void for_each_feature ( state_type s, F && f ) const

inline

calls f( t W H + c ) for each tile t != 0 in each cell c of s

for_each_feature_change()

template<int W, int H>

template<class F>

void for_each_feature_change ( state_type s, state_type t, F && f ) const

inline

calls f( k W H + c ) and f( k W H + b ) for the tile k that the move from s to its successor t slides from the cell c to the cell b of the blank of s

The fields of \( s \oplus t \) hold k in the cells b and c and 0 elsewhere, so that the two cells are found without the blanks.

for_each_nblock_successor()

template<int W, int H>

template<class F>

void for_each_nblock_successor ( std::size_t b, F && f ) const

inline

calls f( b' ) for each abstract successor b' of the nblock b

for_each_successor() [1/2]

template<int W, int H>

template<class F>

void for_each_successor ( state_type s, cost_type h, F && f ) const

inline

calls f( t , 1 , h( t ) ) for each successor t of s

Calls f( t , 1 , h( t ) ) for each successor t of s, h( t ) being computed from h = h( s ) by the change of the moved tile.

for_each_successor() [2/2]

template<int W, int H>

template<class F>

void for_each_successor ( state_type s, cost_type h, std::uint8_t op, F && f ) const

inline

as above, but without the successor that op, the cell where the blank was, leads back to; the operator of a successor is the cell of the blank in s

hash()

template<int W, int H>

std::uint64_t hash ( state_type s ) const

inlinenodiscardnoexcept

the hash of a board: its packed integer, mixed

heuristic()

template<int W, int H>

cost_type heuristic ( state_type s ) const

inlinenodiscardnoexcept

the Manhattan distance of s from the goal

initial_state()

template<int W, int H>

state_type initial_state ( void ) const

inlinenodiscardnoexcept

the start board

is_goal()

template<int W, int H>

bool is_goal ( state_type s ) const

inlinenodiscardnoexcept

true if s is the goal board

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 , ...

nblock()

template<int W, int H>

std::size_t nblock ( state_type s ) const

inlinenodiscardnoexcept

the nblock of PBNF: the cells of the blank and of tiles 1 and 2

num_abstract_features()

template<int W, int H>

constexpr std::size_t num_abstract_features ( void )

inlinestaticnodiscardconstexprnoexcept

the number of abstract features: one per pair ( tile , half board )

num_features()

template<int W, int H>

constexpr std::size_t num_features ( void )

inlinestaticnodiscardconstexprnoexcept

the number of features: one per pair ( tile , cell )

num_nblocks()

template<int W, int H>

constexpr std::size_t num_nblocks ( void )

inlinestaticnodiscardconstexprnoexcept

the number of nblocks: one per triple of cells, not all of them used

pack()

template<int W, int H>

state_type pack ( const board_type & b )

inlinestaticnodiscardnoexcept

packs a board into a word

pairwise_heuristic()

template<int W, int H>

cost_type pairwise_heuristic ( state_type s, state_type t ) const

inlinenodiscardnoexcept

the heuristic of PA*SE: the sum of the displacements of the tiles

parse()

template<int W, int H>

board_type parse ( const std::string & text )

inlinestaticnodiscard

reads a board: W H numbers, the tiles cell by cell, 0 for the blank

perfect_hash()

template<int W, int H>

std::uint64_t perfect_hash ( state_type s ) const

inlinenodiscardnoexcept

the lexicographic rank of the permutation of the cells of the tiles

It is the perfect hash of Korf and Schultze (2005), by which Burns et al. (JAIR 2010) distributed the states of HDA*: as Jinnai and Fukunaga (JAIR 2017) show, modulo the number of processors it depends on very few tiles, and it is kept as a poor work distribution to compare to.

print()

template<int W, int H>

void print ( std::ostream & os, state_type s )

inlinestatic

prints a board, one row per line

tile()

template<int W, int H>

int tile ( state_type s, int c )

inlinestaticnodiscardnoexcept

the tile in the cell c of s

unpack()

template<int W, int H>

board_type unpack ( state_type s )

inlinestaticnodiscardnoexcept

unpacks a word into a board

Member Data Documentation

bits

template<int W, int H>

int bits = cells <= 16 ? 4 : 5

staticconstexpr

the bits of a cell

cells

template<int W, int H>

int cells = W * H

staticconstexpr

the number of cells

height

template<int W, int H>

int height = H

staticconstexpr

the number of rows

width

template<int W, int H>

int width = W

staticconstexpr

the number of columns

---

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

• PBeFS/astar/SlidingTile.h