Search algorithms for the 8-puzzle solution
Public Member Functions | Static Public Member Functions | Private Attributes
GreedySolver Class Reference

Implementation of a greedy exploration algorithm for the 8-puzzle game. More...

#include <GreedySolver.hpp>

Inheritance diagram for GreedySolver:
Collaboration diagram for GreedySolver:

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...
 
- Public Member Functions inherited from Solver
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

Heuristicheuristic
 

Additional Inherited Members

- Protected Member Functions inherited from Solver
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...
 
- Protected Attributes inherited from Solver
OrderedList< GameState * > visited = OrderedList<GameState *>(compare)
 
int visitedNodes
 
int maxDepth
 
int solutionDepth
 
float secondsToSolve
 
bool solved
 

Detailed Description

Implementation of a greedy exploration algorithm for the 8-puzzle game.

Author
Douglas De Rizzo Meneghetti (dougl.nosp@m.asri.nosp@m.zzom@.nosp@m.gmai.nosp@m.l.com)
Date
2017-6-24Implementation of a greedy exploration algorithm for the 8-puzzle game.

Definition at line 15 of file GreedySolver.hpp.

Constructor & Destructor Documentation

◆ GreedySolver()

GreedySolver::GreedySolver ( Heuristic h)
inlineexplicit

Initializes the solver.

Parameters
hthe heuristic to be used by the algorithm

Definition at line 24 of file GreedySolver.hpp.

24  : heuristic(h) {
25  }
Heuristic * heuristic
Here is the caller graph for this function:

◆ ~GreedySolver()

GreedySolver::~GreedySolver ( )
inline

Definition at line 27 of file GreedySolver.hpp.

27  {
28  delete heuristic;
29  }
Heuristic * heuristic

Member Function Documentation

◆ compare()

static int GreedySolver::compare ( GameState a,
GameState b 
)
inlinestatic

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.

Parameters
a
b
Returns
1 if h(a) < h(b), -1 if h(a) > h(b), 0 if h(a) = h(b)

Definition at line 38 of file GreedySolver.hpp.

38  {
39  Manhattan h;
40 
41  if (h.calc(*a) < h.calc(*b)) return 1;
42 
43  if (h.calc(*a) > h.calc(*b)) return - 1;
44 
45  return 0;
46  }
Implementation of the Manhattan distance for the 8-puzzle.
Definition: Heuristic.hpp:23
int calc(GameState &currentState)
Calculates the heuristic value for a state.
Definition: Heuristic.hpp:26
Here is the call graph for this function:

◆ solve()

LinkedList<GameState *> GreedySolver::solve ( Game g,
GameState gs 
)
inlinevirtual

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.

Parameters
gA description of the game.
gsThe initial state of the game.
Returns
list containing all states explored, from the initial state to the goal state.

Implements Solver.

Definition at line 48 of file GreedySolver.hpp.

48  {
49  // like A*, keep the states in an OrderedList, sorted by their heuristic value
50  OrderedList<GameState *> expanded = OrderedList<GameState *>(compare);
51 
52  const clock_t start = clock();
53  expanded.insert(&g0);
54  while (! expanded.isEmpty()) {
55  // need only remove the first element, since they are ordered
56  GameState *currentGame = expanded.remove(0);
57 
58  // check for goal
59  if (*game.getGoal() == *currentGame) {
60  solved=true;
61  return endSearch(currentGame, start);
62  }
63 
64  // expand children
65  LinkedList<GameState *> children = visit(currentGame);
66  while (! children.isEmpty()) {
67  expanded.insert(children.remove(0));
68  }
69  }
70 
71  throw invalid_argument("This game is unsolvable!");
72  }
static int compare(GameState *a, GameState *b)
Compares two states using the available heuristic.
LinkedList< GameState * > endSearch(GameState *currentGame, const clock_t start)
End the search, generating the steps from the initial state to the goal.
Definition: Solver.hpp:91
LinkedList< GameState * > visit(GameState *current)
Definition: Solver.hpp:43
Describes a single state in the 8-puzzle.
Definition: GameState.hpp:18
bool solved
Definition: Solver.hpp:34
Here is the call graph for this function:
Here is the caller graph for this function:

Field Documentation

◆ heuristic

Heuristic* GreedySolver::heuristic
private

Definition at line 18 of file GreedySolver.hpp.


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