Search algorithms for the 8-puzzle solution
|
Implementation of a greedy exploration algorithm for the 8-puzzle game. More...
#include <GreedySolver.hpp>
Public Member Functions | |
GreedySolver (Heuristic *h) | |
Initializes the solver. More... | |
~GreedySolver () | |
LinkedList< GameState * > | solve (Game &game, GameState &g0) |
Explores the game tree in search of the goal state. More... | |
![]() | |
double | getSecondsToSolve () const |
int | getVisitedNodes () const |
int | getMaxDepth () const |
int | getSolutionDepth () const |
bool | isSolved () |
Solver () | |
string | to_string () |
Generates a string containing useful information from the solver run. More... | |
Static Public Member Functions | |
static int | compare (GameState *a, GameState *b) |
Compares two states using the available heuristic. More... | |
Private Attributes | |
Heuristic * | heuristic |
Additional Inherited Members | |
![]() | |
bool | isVisited (GameState &g) |
Checks whether a node has already been visited by the solver. More... | |
LinkedList< GameState * > | visit (GameState *current) |
LinkedList< GameState * > | visit (GameState *current, bool keepVisited) |
Visit a game state, adding it to the list of visited states and returning its valid child states. More... | |
LinkedList< GameState * > | endSearch (GameState *currentGame, const clock_t start) |
End the search, generating the steps from the initial state to the goal. More... | |
![]() | |
OrderedList< GameState * > | visited = OrderedList<GameState *>(compare) |
int | visitedNodes |
int | maxDepth |
int | solutionDepth |
float | secondsToSolve |
bool | solved |
Implementation of a greedy exploration algorithm for the 8-puzzle game.
Definition at line 15 of file GreedySolver.hpp.
|
inlineexplicit |
Initializes the solver.
h | the heuristic to be used by the algorithm |
Definition at line 24 of file GreedySolver.hpp.
|
inline |
Definition at line 27 of file GreedySolver.hpp.
Compares two states using the available heuristic.
The greedy search takes into consideration only the sum of Manhattan distances between pieces in the current state to their goal state. The state that has the lowest heuristic is considered a more promising exploration candidate.
a | |
b |
Definition at line 38 of file GreedySolver.hpp.
Explores the game tree in search of the goal state.
Exploration is done by applying one of the four valid actions of the 8-puzzle to intermediate, non-goal states until the goal state is reached.
g | A description of the game. |
gs | The initial state of the game. |
Implements Solver.
Definition at line 48 of file GreedySolver.hpp.
|
private |
Definition at line 18 of file GreedySolver.hpp.