NQueens.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*----------------------------- File NQueens.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_NQueens
 #define __PBeFS_NQueens
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <array>
 
#include <cstddef>
 
#include <cstdint>
 
#include <cstdlib>
 
#include <cstring>
 
#include <stdexcept>
 
#include "PBeFS/astar/Domain.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS NQueens ------------------------------*/
/*--------------------------------------------------------------------------*/

 
class NQueens {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/

 struct Board {
  std::array< std::uint8_t , 32 > row;   
  std::uint8_t k;                        
 
  bool operator==( const Board & ) const = default;
  };
 
 using state_type = Board;                       
 using cost_type = int;                          
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit NQueens( int n ) : f_n( n ) {
  if( ( n < 1 ) || ( n > 32 ) )
   throw( std::invalid_argument( "NQueens::NQueens: n is 1 to 32" ) );
  }
 
/*------------------------- METHODS OF THE DOMAIN --------------------------*/
 
 [[nodiscard]] Board initial_state( void ) const noexcept {
  return( Board{ {} , 0 } );
  }
 
 [[nodiscard]] bool is_goal( const Board & s ) const noexcept {
  return( s.k == f_n );
  }
 
 [[nodiscard]] std::uint64_t hash( const Board & s ) const noexcept {
  std::uint64_t w[ 4 ];
  std::memcpy( w , s.row.data() , sizeof( w ) );
  std::uint64_t z = ADS::splitmix64( s.k );
  for( std::uint64_t x : w )
   z = ADS::splitmix64( z ^ x );
  return( z );
  }
 
 [[nodiscard]] int heuristic( const Board & s ) const noexcept {
  return( f_n - s.k );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_successor( const Board & s , int h , F && f ) const {
  const int k = s.k;
  for( int r = 0 ; r < f_n ; ++r ) {
   bool free = true;
   for( int c = 0 ; free && ( c < k ) ; ++c ) {
    const int rc = s.row[ c ];
    free = ( rc != r ) && ( std::abs( rc - r ) != k - c );
    }
   if( free ) {
    Board t = s;
    t.row[ k ] = std::uint8_t( r );
    t.k = std::uint8_t( k + 1 );
    f( t , 1 , h - 1 );
    }
   }
  }
 
/*---------------------- FEATURES FOR ZOBRIST HASHING ----------------------*/
 
 [[nodiscard]] std::size_t num_features( void ) const noexcept {
  return( std::size_t( f_n ) * f_n );
  }

 
 template< class F >
 void for_each_feature( const Board & s , F && f ) const {
  for( int c = 0 ; c < s.k ; ++c )
   f( std::size_t( c ) * f_n + s.row[ c ] );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int size( void ) const noexcept { return( f_n ); }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 int f_n;                                        
 
 };  // end( class( NQueens ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_NQueens */
 
/*--------------------------------------------------------------------------*/
/*--------------------------- End File NQueens.h ---------------------------*/
/*--------------------------------------------------------------------------*/