the sliding-tile puzzle with an additive pattern database heuristic More...

#include <PBeFS/astar/PatternDatabase.h>

Inheritance diagram for SlidingTilePDB< W, H, Enc >:

Public Types
using	Base = SlidingTile< W , H >
	the puzzle
using	PDB = AdditivePDB< W , H , Enc >
	the heuristic
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 Types inherited from SlidingTile< W, H >
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
	SlidingTilePDB (const board_type &start, const PDB &pdb)
	constructor, taking the start board and the heuristic
cost_type	heuristic (state_type s) const
	the heuristic of s, looked up in the tables
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 leads back to [see SlidingTile]
const PDB &	pdb (void) const noexcept
	the heuristic
Public Member Functions inherited from SlidingTile< W, H >
	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 void	cells_of (state_type s, std::uint8_t *q) noexcept
	writes in q the cell of each tile of s
Static Public Member Functions inherited from SlidingTile< W, H >
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	cells = Base::cells
	the cells
Static Public Attributes inherited from SlidingTile< W, H >
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 Enc = NibbleEntries>
class PBeFS_di_unipi_it::SlidingTilePDB< W, H, Enc >

the sliding-tile puzzle with an additive pattern database heuristic

The domain SlidingTile, with all its features, hashes and abstractions, whose heuristic is that of an AdditivePDB (which must outlive it) in place of the Manhattan distance; the goal is that of the tables. With Mod3Entries the heuristic of a successor is that of its parent plus the change of the table of the tile moved, which the residues give, and only the initial state is looked up from the residues alone; this needs the sum without the reflection, since from the maximum of two sums the parts cannot be told apart.