DepthFirstSolver Class Reference

8-puzzle exploration based on a depth-first search strategy More...

#include <DepthFirstSolver.hpp>

Inheritance diagram for DepthFirstSolver:

Collaboration diagram for DepthFirstSolver:

Public Member Functions
	DepthFirstSolver ()
	DepthFirstSolver (int maxDepth)
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...

Private Attributes
int	maxDepth

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

8-puzzle exploration based on a depth-first search strategy

Author

Douglas De Rizzo Meneghetti (dougl.nosp@m.asri.nosp@m.zzom@.nosp@m.gmai.nosp@m.l.com)

Date

2017-6-238-puzzle exploration based on a depth-first search strategy

Definition at line 16 of file DepthFirstSolver.hpp.

Constructor & Destructor Documentation

DepthFirstSolver() [1/2]

DepthFirstSolver::DepthFirstSolver ( )

inline

Definition at line 23 of file DepthFirstSolver.hpp.

                     : maxDepth(- 1) {
    // no limits in depth
  }

Here is the caller graph for this function:

DepthFirstSolver() [2/2]

DepthFirstSolver::DepthFirstSolver ( int  maxDepth )

inlineexplicit

Parameters

maxDepth

the maximum depth allowed for exploration

Definition at line 28 of file DepthFirstSolver.hpp.

                                          : maxDepth(maxDepth > - 1 ? maxDepth : - 1) {
  }

Member Function Documentation

solve()

LinkedList<GameState *> DepthFirstSolver::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

g	A description of the game.
gs	The initial state of the game.

Returns

list containing all states explored, from the initial state to the goal state.

Implements Solver.

Definition at line 31 of file DepthFirstSolver.hpp.

                                                           {
    // use a stack to organize states, states that were reached last will be the
    // first ones to be evaluated
    DynamicStack<GameState *> expanded;

    const clock_t start = clock();
    expanded.push(&g0);
    int currentMaxDepth = 0;

    while (! expanded.isEmpty()) {
      GameState *currentGame = expanded.pop();

      if (currentGame->getDepth() > currentMaxDepth) {
        currentMaxDepth = currentGame->getDepth();
      }

      // useful only for debugging
      // cout << currentGame->getDepth() << '\t' << visited.getSize() << '\t' << expanded.getSize() << endl;

      // check for goal
      if (*game.getGoal() == *currentGame) {
        solved = true;
        return endSearch(currentGame, start);
      }

      // expand children, but check the maximum allowed depth before inserting
      // them in the exploration stack
      LinkedList<GameState *> children = visit(currentGame);

      if ((maxDepth == - 1) || (currentGame->getDepth() < maxDepth)) {
        while (! children.isEmpty()) {
          expanded.push(children.remove(0));
        }
      }
    }
    throw invalid_argument("This game is unsolvable!");
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

maxDepth

int DepthFirstSolver::maxDepth

private

Definition at line 19 of file DepthFirstSolver.hpp.

---

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

• include/DepthFirstSolver.hpp