SlidingTile.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*--------------------------- File SlidingTile.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_SlidingTile
 #define __PBeFS_SlidingTile
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <array>
 
#include <bit>
 
#include <cstddef>
 
#include <cstdint>
 
#include <cstdlib>
 
#include <ostream>
 
#include <sstream>
 
#include <stdexcept>
 
#include <string>
 
#include <type_traits>
 
#include "PBeFS/astar/Domain.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS Word128 ------------------------------*/
/*--------------------------------------------------------------------------*/

 
struct Word128 {
 
 std::uint64_t lo = 0;                           
 std::uint64_t hi = 0;                           
 
 constexpr Word128( void ) noexcept = default;

 
 constexpr Word128( std::uint64_t l ) noexcept : lo( l ) {}

 
 constexpr Word128( std::uint64_t l , std::uint64_t h ) noexcept
  : lo( l ) , hi( h ) {}

 
 explicit constexpr operator std::uint64_t( void ) const noexcept {
  return( lo );
  }
 
 friend constexpr bool operator==( const Word128 & a , const Word128 & b )
  noexcept = default;
 
 friend constexpr Word128 operator&( Word128 a , Word128 b ) noexcept {
  return( Word128( a.lo & b.lo , a.hi & b.hi ) );
  }
 
 friend constexpr Word128 operator|( Word128 a , Word128 b ) noexcept {
  return( Word128( a.lo | b.lo , a.hi | b.hi ) );
  }
 
 friend constexpr Word128 operator^( Word128 a , Word128 b ) noexcept {
  return( Word128( a.lo ^ b.lo , a.hi ^ b.hi ) );
  }
 
 friend constexpr Word128 operator~( Word128 a ) noexcept {
  return( Word128( ~a.lo , ~a.hi ) );
  }

 
 friend constexpr Word128 operator<<( Word128 a , int n ) noexcept {
  if( n == 0 )
   return( a );
  if( n >= 64 )
   return( Word128( 0 , a.lo << ( n - 64 ) ) );
  return( Word128( a.lo << n , ( a.hi << n ) | ( a.lo >> ( 64 - n ) ) ) );
  }

 
 friend constexpr Word128 operator>>( Word128 a , int n ) noexcept {
  if( n == 0 )
   return( a );
  if( n >= 64 )
   return( Word128( a.hi >> ( n - 64 ) , 0 ) );
  return( Word128( ( a.lo >> n ) | ( a.hi << ( 64 - n ) ) , a.hi >> n ) );
  }
 
 Word128 & operator|=( Word128 b ) noexcept { return( *this = *this | b ); }

 
 [[nodiscard]] friend constexpr int countr_zero( Word128 a ) noexcept {
  return( a.lo ? std::countr_zero( a.lo ) : 64 + std::countr_zero( a.hi ) );
  }
 
 };  // end( struct( Word128 ) )
 
/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS SlidingTile ----------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int W , int H >
class SlidingTile {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 static constexpr int width = W;           
 static constexpr int height = H;          
 static constexpr int cells = W * H;       
 
 static_assert( ( W >= 2 ) && ( H >= 2 ) && ( cells <= 25 ) ,
                "SlidingTile: the packed state holds at most 25 cells" );
 
 static constexpr int bits = cells <= 16 ? 4 : 5;  
 
 using state_type = std::conditional_t< cells <= 16 , std::uint64_t ,
                                        Word128 >;  
 using cost_type = int;                    
 using board_type = std::array< std::uint8_t , cells >;  
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 [[nodiscard]] static board_type korf_goal( void ) {
  board_type b{};
  for( int i = 0 ; i < cells ; ++i )
   b[ i ] = static_cast< std::uint8_t >( i );
  return( b );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 explicit SlidingTile( const board_type & start ,
                       const board_type & goal = korf_goal() )
  : f_start( pack( check( start ) ) ) , f_goal( pack( check( goal ) ) ) {
  if( parity( start ) != parity( goal ) )
   throw( std::invalid_argument( "SlidingTile::SlidingTile: the goal is "
                                 "not reachable from the start" ) );
  for( int c = 0 ; c < cells ; ++c )
   v_goal_cell[ goal[ c ] ] = c;
  for( int t = 1 ; t < cells ; ++t )
   for( int c = 0 ; c < cells ; ++c )
    v_md[ t ][ c ] = distance( c , v_goal_cell[ t ] );
  for( int b = 0 ; b < cells ; ++b ) {
   const int r = b / W , k = b % W;
   Moves & o = v_moves[ b ];
   if( r > 0 )
    o.cell[ o.n++ ] = b - W;
   if( k > 0 )
    o.cell[ o.n++ ] = b - 1;
   if( k < W - 1 )
    o.cell[ o.n++ ] = b + 1;
   if( r < H - 1 )
    o.cell[ o.n++ ] = b + W;
   }
  }
 
/*------------------------- METHODS OF THE DOMAIN --------------------------*/
 
 [[nodiscard]] state_type initial_state( void ) const noexcept {
  return( f_start );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] bool is_goal( state_type s ) const noexcept {
  return( s == f_goal );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::uint64_t hash( state_type s ) const noexcept {
  if constexpr( cells <= 16 )
   return( ADS::splitmix64( s ) );
  else
   return( ADS::splitmix64( s.lo ^ ADS::splitmix64( s.hi ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] cost_type heuristic( state_type s ) const noexcept {
  int h = 0;
  for( int c = 0 ; c < cells ; ++c )
   h += v_md[ tile( s , c ) ][ c ];
  return( h );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 template< class F >
 void for_each_successor( state_type s , cost_type h , F && f ) const {
  const int b = blank( s );
  const Moves & o = v_moves[ b ];
  for( int i = 0 ; i < o.n ; ++i ) {
   const int c = o.cell[ i ];
   const int t = tile( s , c );
   const state_type child = ( s & ~( state_type( c_tile ) << ( bits * c ) ) )
                            | ( state_type( t ) << ( bits * b ) );
   f( child , 1 , h + v_md[ t ][ b ] - v_md[ t ][ c ] );
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_successor( state_type s , cost_type h , std::uint8_t op ,
                          F && f ) const {
  const int b = blank( s );
  const Moves & o = v_moves[ b ];
  for( int i = 0 ; i < o.n ; ++i ) {
   const int c = o.cell[ i ];
   if( c == op )
    continue;
   const int t = tile( s , c );
   const state_type child = ( s & ~( state_type( c_tile ) << ( bits * c ) ) )
                            | ( state_type( t ) << ( bits * b ) );
   f( child , 1 , h + v_md[ t ][ b ] - v_md[ t ][ c ] , std::uint8_t( b ) );
   }
  }
 
/*---------------------- FEATURES FOR ZOBRIST HASHING ----------------------*/
 
 [[nodiscard]] static constexpr std::size_t num_features( void ) noexcept {
  return( std::size_t( cells ) * cells );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_feature( state_type s , F && f ) const {
  for( int c = 0 ; c < cells ; ++c )
   if( const int t = tile( s , c ) )
    f( std::size_t( t * cells + c ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 template< class F >
 void for_each_feature_change( state_type s , state_type t , F && f ) const {
  const state_type d = s ^ t;
  if( d == state_type( 0 ) )
   return;
  using std::countr_zero;
  const int i = countr_zero( d ) / bits;
  const int k = tile( d , i );
  const int j =
   countr_zero( d & ~( state_type( c_tile ) << ( bits * i ) ) ) / bits;
  f( std::size_t( k * cells + i ) );
  f( std::size_t( k * cells + j ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static constexpr std::size_t num_abstract_features( void )
  noexcept {
  return( std::size_t( cells ) * 2 );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static constexpr std::size_t abstract_feature( std::size_t i )
  noexcept {
  const std::size_t t = i / cells , c = i % cells;
  return( t * 2 + ( c / W >= H / 2 ? 1 : 0 ) );
  }
 
/*--------------------------- STATE ABSTRACTIONS ---------------------------*/
 
 [[nodiscard]] std::uint64_t abstract_state( state_type s ) const noexcept {
  int p[ 4 ] = { 0 , 0 , 0 , 0 };
  for( int c = 0 ; c < cells ; ++c )
   if( const int t = tile( s , c ) ; ( t >= 1 ) && ( t <= 3 ) )
    p[ t ] = c;
  return( ( std::uint64_t( p[ 1 ] ) * cells + p[ 2 ] ) * cells + p[ 3 ] );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static constexpr std::size_t num_nblocks( void ) noexcept {
  return( std::size_t( cells ) * cells * cells );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::size_t nblock( state_type s ) const noexcept {
  int p[ 3 ] = { 0 , 0 , 0 };
  for( int c = 0 ; c < cells ; ++c )
   if( const int t = tile( s , c ) ; t <= 2 )
    p[ t ] = c;
  return( nblock_id( p[ 0 ] , p[ 1 ] , p[ 2 ] ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_nblock_successor( std::size_t b , F && f ) const {
  const int p2 = int( b % cells );
  const int p1 = int( b / cells % cells );
  const int p0 = int( b / cells / cells );
  if( ( p0 == p1 ) || ( p0 == p2 ) || ( p1 == p2 ) )
   return;                                    // not an abstract state
  const Moves & o = v_moves[ p0 ];
  for( int i = 0 ; i < o.n ; ++i ) {
   const int c = o.cell[ i ];
   if( c == p1 )
    f( nblock_id( c , p0 , p2 ) );
   else
    if( c == p2 )
     f( nblock_id( c , p1 , p0 ) );
    else
     f( nblock_id( c , p1 , p2 ) );
   }
  }
 
/*---------------------- OTHER HEURISTICS AND HASHES -----------------------*/
 
 [[nodiscard]] cost_type pairwise_heuristic( state_type s , state_type t )
  const noexcept {
  int ps[ cells ] , pt[ cells ];
  for( int c = 0 ; c < cells ; ++c ) {
   ps[ tile( s , c ) ] = c;
   pt[ tile( t , c ) ] = c;
   }
  int h = 0;
  for( int k = 1 ; k < cells ; ++k )
   h += distance( ps[ k ] , pt[ k ] );
  return( h );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] std::uint64_t perfect_hash( state_type s ) const noexcept
  requires( cells <= 20 ) {
  int pos[ cells ];
  for( int c = 0 ; c < cells ; ++c )
   pos[ tile( s , c ) ] = c;
  std::uint64_t rank = 0;
  std::uint32_t used = 0;
  for( int k = 0 ; k < cells ; ++k ) {
   const std::uint32_t below = used & ( ( 1u << pos[ k ] ) - 1u );
   rank = rank * std::uint64_t( cells - k ) +
          std::uint64_t( pos[ k ] - std::popcount( below ) );
   used |= 1u << pos[ k ];
   }
  return( rank );
  }
 
/*----------------------------- BOARD HELPERS ------------------------------*/
 
 [[nodiscard]] static int tile( state_type s , int c ) noexcept {
  return( int( std::uint64_t( s >> ( bits * c ) ) & c_tile ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] static int blank( state_type s ) noexcept {
  state_type t = s;
  for( int k = 1 ; k < bits ; ++k )
   t |= s >> k;
  t = ~t & c_low_bits;
  using std::countr_zero;
  return( countr_zero( t ) / bits );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static state_type pack( const board_type & b ) noexcept {
  state_type s = 0;
  for( int c = 0 ; c < cells ; ++c )
   s |= state_type( b[ c ] ) << ( bits * c );
  return( s );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static board_type unpack( state_type s ) noexcept {
  board_type b{};
  for( int c = 0 ; c < cells ; ++c )
   b[ c ] = static_cast< std::uint8_t >( tile( s , c ) );
  return( b );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static board_type parse( const std::string & text ) {
  std::istringstream in( text );
  board_type b{};
  for( int c = 0 ; c < cells ; ++c ) {
   int t = -1;
   if( ! ( in >> t ) || ( t < 0 ) || ( t >= cells ) )
    throw( std::invalid_argument( "SlidingTile::parse: bad board" ) );
   b[ c ] = static_cast< std::uint8_t >( t );
   }
  return( check( b ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 static void print( std::ostream & os , state_type s ) {
  for( int r = 0 ; r < H ; ++r ) {
   for( int k = 0 ; k < W ; ++k ) {
    const int t = tile( s , r * W + k );
    if( t == 0 )
     os << "   ";
    else
     os << ( t < 10 ? "  " : " " ) << t;
    }
   os << '\n';
   }
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 struct Moves {
  int n = 0;
  int cell[ 4 ] = { 0 , 0 , 0 , 0 };
  };

 static constexpr std::uint64_t c_tile = ( std::uint64_t( 1 ) << bits ) - 1;

 static constexpr state_type c_low_bits = [] {
  state_type m = 0;
  for( int c = 0 ; c < cells ; ++c )
   m = m | ( state_type( 1 ) << ( bits * c ) );
  return( m );
  }();
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the Manhattan distance between two cells
 
 static int distance( int a , int b ) noexcept {
  return( std::abs( a / W - b / W ) + std::abs( a % W - b % W ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the index of the nblock with the blank in p0 and tiles 1 , 2 in p1 , p2
 
 static std::size_t nblock_id( int p0 , int p1 , int p2 ) noexcept {
  return( ( std::size_t( p0 ) * cells + p1 ) * cells + p2 );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // throws unless b is a permutation of 0 , ... , cells - 1
 
 static const board_type & check( const board_type & b ) {
  std::uint32_t seen = 0;
  for( std::uint8_t t : b ) {
   if( ( t >= cells ) || ( ( seen >> t ) & 1u ) )
    throw( std::invalid_argument( "SlidingTile::check: not a permutation" )
           );
   seen |= 1u << t;
   }
  return( b );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the invariant of solvability: the parity of the permutation of the tiles
 // plus, on boards of even width, the row of the blank
 
 static int parity( const board_type & b ) noexcept {
  int inv = 0 , blank_row = 0;
  for( int i = 0 ; i < cells ; ++i ) {
   if( b[ i ] == 0 ) {
    blank_row = i / W;
    continue;
    }
   for( int j = i + 1 ; j < cells ; ++j )
    if( b[ j ] && ( b[ j ] < b[ i ] ) )
     ++inv;
   }
  return( ( W % 2 == 1 ? inv : inv + blank_row ) % 2 );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 state_type f_start;                             
 state_type f_goal;                              
 int v_goal_cell[ cells ] = {};                  
 int v_md[ cells ][ cells ] = {};    
 Moves v_moves[ cells ];                    
 
 };  // end( class( SlidingTile ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
using EightPuzzle = SlidingTile< 3 , 3 >;       
using FifteenPuzzle = SlidingTile< 4 , 4 >;     
using TwentyFourPuzzle = SlidingTile< 5 , 5 >;  
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_SlidingTile */
 
/*--------------------------------------------------------------------------*/
/*------------------------- End File SlidingTile.h -------------------------*/
/*--------------------------------------------------------------------------*/