machine_learning::aystar_search::EightPuzzle< N > Class Template Reference

A class defining EightPuzzle/15-Puzzle game. More...

Collaboration diagram for machine_learning::aystar_search::EightPuzzle< N >:

Public Member Functions
uint32_t	get (size_t i, size_t j) const
	get the value from i units from right and j units from left side of the board
std::array< std::array< uint32_t, N >, N >	get_state ()
	Returns the current state of the board.
size_t	get_size () const
	returns the size of the EightPuzzle (number of row / column)
	EightPuzzle ()
	Default constructor for EightPuzzle.
	EightPuzzle (const std::array< std::array< uint32_t, N >, N > &init)
	Parameterized Constructor for EightPuzzle.
	EightPuzzle (const EightPuzzle< N > &A)
	Copy constructor.
	EightPuzzle (const EightPuzzle< N > &&A) noexcept
	Move constructor.
	~EightPuzzle ()=default
	Destructor of EightPuzzle.
EightPuzzle &	operator= (const EightPuzzle &A)
	Copy assignment operator.
EightPuzzle &	operator= (EightPuzzle &&A) noexcept
	Move assignment operator.
std::vector< EightPuzzle< N > >	generate_possible_moves ()
	Find all possible states after processing all possible moves, given the current state of the puzzle.
bool	operator== (const EightPuzzle< N > &check) const
	check whether two boards are equal
bool	operator< (const EightPuzzle< N > &check) const
	check whether one board is lexicographically smaller
bool	operator<= (const EightPuzzle< N > &check) const
	check whether one board is lexicographically smaller or equal

Private Member Functions
std::pair< uint32_t, uint32_t >	find_zero ()
	A helper array to evaluate the next state from current state;.
bool	in_range (const uint32_t value) const
	check whether the index value is bounded within the puzzle area

Private Attributes
std::array< std::array< uint32_t, N >, N >	board
std::vector< std::pair< int8_t, int8_t > >	moves
	N x N array to store the current state of the Puzzle.

Friends
std::ostream &	operator<< (std::ostream &op, const EightPuzzle< N > &SomeState)
	friend operator to display EightPuzzle<>

Detailed Description

template<size_t N = 3>
class machine_learning::aystar_search::EightPuzzle< N >

A class defining EightPuzzle/15-Puzzle game.

A well known 3 x 3 puzzle of the form 1 2 3 4 5 6 7 8 0 where 0 represents an empty space in the puzzle Given any random state, the goal is to achieve the above configuration (or any other configuration if possible)

Template Parameters

N	size of the square Puzzle, default is set to 3 (since it is EightPuzzle)

Constructor & Destructor Documentation

EightPuzzle() [1/4]

template<size_t N = 3>

machine_learning::aystar_search::EightPuzzle< N >::EightPuzzle ( )

inline

Default constructor for EightPuzzle.

                  {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                board[i][j] = ((i * 3 + j + 1) % (N * N));
            }
        }
    }

EightPuzzle() [2/4]

template<size_t N = 3>

machine_learning::aystar_search::EightPuzzle< N >::EightPuzzle ( const std::array< std::array< uint32_t, N >, N > & init )

inlineexplicit

Parameterized Constructor for EightPuzzle.

Parameters

init	a 2-dimensional array denoting a puzzle configuration

        : board(init) {}

EightPuzzle() [3/4]

template<size_t N = 3>

machine_learning::aystar_search::EightPuzzle< N >::EightPuzzle ( const EightPuzzle< N > & A )

inline

Copy constructor.

Parameters

A	a reference of an EightPuzzle

: board(A.board) {}

EightPuzzle() [4/4]

template<size_t N = 3>

machine_learning::aystar_search::EightPuzzle< N >::EightPuzzle ( const EightPuzzle< N > && A )

inlinenoexcept

Move constructor.

Parameters

A	a reference of an EightPuzzle

        : board(std::move(A.board)) {}

Member Function Documentation

find_zero()

template<size_t N = 3>

std::pair< uint32_t, uint32_t > machine_learning::aystar_search::EightPuzzle< N >::find_zero ( )

inlineprivate

A helper array to evaluate the next state from current state;.

Finds an empty space in puzzle (in this case; a zero)

Returns

a pair indicating integer distances from top and right respectively, else returns -1, -1

                                            {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (!board[i][j]) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }

generate_possible_moves()

template<size_t N = 3>

std::vector< EightPuzzle< N > > machine_learning::aystar_search::EightPuzzle< N >::generate_possible_moves ( )

inline

Find all possible states after processing all possible moves, given the current state of the puzzle.

Returns

list of vector containing all possible next moves

Note

the implementation is compulsory to create A* search

                                                        {
        auto zero_pos = find_zero();
        // vector which will contain all possible state from current state
        std::vector<EightPuzzle<N>> NewStates;
        for (auto &move : moves) {
            if (in_range(zero_pos.first + move.first) &&
                in_range(zero_pos.second + move.second)) {
                // swap with the possible moves
                std::array<std::array<uint32_t, N>, N> new_config = board;
                std::swap(new_config[zero_pos.first][zero_pos.second],
                          new_config[zero_pos.first + move.first]
                                    [zero_pos.second + move.second]);
                EightPuzzle<N> new_state(new_config);
                // Store new state and calculate heuristic value, and depth
                NewStates.emplace_back(new_state);
            }
        }
        return NewStates;
    }

Here is the call graph for this function:

get()

template<size_t N = 3>

uint32_t machine_learning::aystar_search::EightPuzzle< N >::get ( size_t i, size_t j ) const

inline

get the value from i units from right and j units from left side of the board

Parameters

i	integer denoting ith row
j	integer denoting column

Returns

non-negative integer denoting the value at ith row and jth column

-1 if invalid i or j position

                                           {
        if (in_range(i) && in_range(j)) {
            return board[i][j];
        }
        return -1;
    }

Here is the call graph for this function:

get_size()

template<size_t N = 3>

size_t machine_learning::aystar_search::EightPuzzle< N >::get_size ( ) const

inline

returns the size of the EightPuzzle (number of row / column)

Returns

N, the size of the puzzle.

{ return N; }

get_state()

template<size_t N = 3>

std::array< std::array< uint32_t, N >, N > machine_learning::aystar_search::EightPuzzle< N >::get_state ( )

inline

Returns the current state of the board.

{ return board; }

in_range()

template<size_t N = 3>

bool machine_learning::aystar_search::EightPuzzle< N >::in_range ( const uint32_t value ) const

inlineprivate

check whether the index value is bounded within the puzzle area

Parameters

value

index for the current board

Returns

true if index is within the board, else false

{ return value < N; }

operator<()

template<size_t N = 3>

bool machine_learning::aystar_search::EightPuzzle< N >::operator< ( const EightPuzzle< N > & check ) const

inline

check whether one board is lexicographically smaller

Returns

true if this->state is lexicographically smaller than check.state, else false

                                                      {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (board[i][j] != check.board[i][j]) {
                    return board[i][j] < check.board[i][j];
                }
            }
        }
        return false;
    }

operator<=()

template<size_t N = 3>

bool machine_learning::aystar_search::EightPuzzle< N >::operator<= ( const EightPuzzle< N > & check ) const

inline

check whether one board is lexicographically smaller or equal

Returns

true if this->state is lexicographically smaller than check.state or same, else false

                                                       {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (board[i][j] != check.board[i][j]) {
                    return board[i][j] < check.board[i][j];
                }
            }
        }
        return true;
    }

operator=() [1/2]

template<size_t N = 3>

EightPuzzle & machine_learning::aystar_search::EightPuzzle< N >::operator= ( const EightPuzzle< N > & A )

inline

Copy assignment operator.

Parameters

A	a reference of an EightPuzzle

                                                 {
        board = A.board;
        return *this;
    }

operator=() [2/2]

template<size_t N = 3>

EightPuzzle & machine_learning::aystar_search::EightPuzzle< N >::operator= ( EightPuzzle< N > && A )

inlinenoexcept

Move assignment operator.

Parameters

A	a reference of an EightPuzzle

                                                     {
        board = std::move(A.board);
        return *this;
    }

Here is the call graph for this function:

operator==()

template<size_t N = 3>

bool machine_learning::aystar_search::EightPuzzle< N >::operator== ( const EightPuzzle< N > & check ) const

inline

check whether two boards are equal

Returns

true if check.state is equal to this->state, else false

                                                       {
        if (check.get_size() != N) {
            return false;
        }
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (board[i][j] != check.board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

Friends And Related Symbol Documentation

operator<<

template<size_t N = 3>

std::ostream & operator<< ( std::ostream & op, const EightPuzzle< N > & SomeState )

friend

friend operator to display EightPuzzle<>

Parameters

op	ostream object
SomeState	a certain state.

Returns

ostream operator op

                                                                     {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                op << SomeState.board[i][j] << " ";
            }
            op << "\n";
        }
        return op;
    }

Member Data Documentation

moves

template<size_t N = 3>

std::vector<std::pair<int8_t, int8_t> > machine_learning::aystar_search::EightPuzzle< N >::moves

private

Initial value:

= {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1,
         0}}

N x N array to store the current state of the Puzzle.

                                               {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1,
         0}};  /// A helper array to evaluate the next state from current state;

---

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

• machine_learning/a_star_search.cpp