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)

Definition at line 62 of file a_star_search.cpp.

Constructor & Destructor Documentation

EightPuzzle() [1/4]

template<size_t N = 3>

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

inline

Default constructor for EightPuzzle.

Definition at line 123 of file a_star_search.cpp.

                  {
        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

Definition at line 134 of file a_star_search.cpp.

        : 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

Definition at line 141 of file a_star_search.cpp.

: 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

Definition at line 147 of file a_star_search.cpp.

        : 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

Definition at line 77 of file a_star_search.cpp.

                                            {
        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

Definition at line 178 of file a_star_search.cpp.

                                                        {
        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;
    }

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

Definition at line 104 of file a_star_search.cpp.

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

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.

Definition at line 119 of file a_star_search.cpp.

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

Definition at line 113 of file a_star_search.cpp.

{ 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

Definition at line 92 of file a_star_search.cpp.

{ 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

Definition at line 220 of file a_star_search.cpp.

                                                      {
        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

Definition at line 235 of file a_star_search.cpp.

                                                       {
        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

Definition at line 158 of file a_star_search.cpp.

                                                 {
        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

Definition at line 167 of file a_star_search.cpp.

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

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

Definition at line 202 of file a_star_search.cpp.

                                                       {
        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

Definition at line 252 of file a_star_search.cpp.

                                                                     {
        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

board

template<size_t N = 3>

std::array<std::array<uint32_t, N>, N> machine_learning::aystar_search::EightPuzzle< N >::board

private

Definition at line 64 of file a_star_search.cpp.

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.

Definition at line 66 of file a_star_search.cpp.

                                               {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1,
         0}};  

---

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

• machine_learning/a_star_search.cpp