Solver Class Reference

Base class for all 8-puzzle solvers. More...

#include <Solver.hpp>

Inheritance diagram for Solver:

Collaboration diagram for Solver:

Public Member Functions
double	getSecondsToSolve () const
int	getVisitedNodes () const
int	getMaxDepth () const
int	getSolutionDepth () const
bool	isSolved ()
	Solver ()
virtual LinkedList< GameState * >	solve (Game &g, GameState &gs)=0
	Explores the game tree in search of the goal state. More...
string	to_string ()
	Generates a string containing useful information from the solver run. More...

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

Static Private Member Functions
static int	compare (GameState *a, GameState *b)

Detailed Description

Base class for all 8-puzzle solvers.

Author

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

Date

2017-6-22Base class for all 8-puzzle solvers.

Definition at line 17 of file Solver.hpp.

Constructor & Destructor Documentation

Solver()

Solver::Solver ( )

inline

Definition at line 133 of file Solver.hpp.

           {
    visited = OrderedList<GameState *>(compare);
    secondsToSolve = visitedNodes = maxDepth = solutionDepth = 0;
    solved = false;
  }

Here is the call graph for this function:

Member Function Documentation

compare()

static int Solver::compare ( GameState *  a, GameState *  b  )

inlinestaticprivate

Definition at line 20 of file Solver.hpp.

                                                 {
    return *a < *b;
  }

Here is the call graph for this function:

endSearch()

LinkedList<GameState *> Solver::endSearch ( GameState *  currentGame, const clock_t  start  )

inlineprotected

End the search, generating the steps from the initial state to the goal.

Parameters

currentGame	the state containing the goal
start	the time the solve began, in order to calculate its time

Returns

list containing the steps from the initial state to the goal

Definition at line 91 of file Solver.hpp.

                                                                                 {
    secondsToSolve = float(clock() - start) / CLOCKS_PER_SEC;

    LinkedList<GameState *> resultSteps;

    GameState *tmp = currentGame;
    solutionDepth = currentGame->getDepth();

    // memoryless process don't work with a list of visited nodes, they
    // increment this variable on the fly
    visitedNodes = visitedNodes != 0 ? visitedNodes : visited.getSize();

    while (tmp != NULL) {
      resultSteps.insert(tmp, resultSteps.getSize());
      tmp = tmp->getParent();
    }

    return resultSteps;
  }

Here is the call graph for this function:

getMaxDepth()

int Solver::getMaxDepth ( ) const

inline

Definition at line 121 of file Solver.hpp.

                          {
    return maxDepth;
  }

Here is the call graph for this function:

getSecondsToSolve()

double Solver::getSecondsToSolve ( ) const

inline

Definition at line 113 of file Solver.hpp.

                                   {
    return secondsToSolve;
  }

Here is the call graph for this function:

getSolutionDepth()

int Solver::getSolutionDepth ( ) const

inline

Definition at line 125 of file Solver.hpp.

                               {
    return solutionDepth;
  }

Here is the call graph for this function:

getVisitedNodes()

int Solver::getVisitedNodes ( ) const

inline

Definition at line 117 of file Solver.hpp.

                              {
    return visitedNodes;
  }

Here is the call graph for this function:

isSolved()

bool Solver::isSolved ( )

inline

Definition at line 129 of file Solver.hpp.

                  {
    return solved;
  }

Here is the call graph for this function:

isVisited()

bool Solver::isVisited ( GameState &  g )

inlineprotected

Checks whether a node has already been visited by the solver.

Parameters

g	The state to look for

Returns

true if g has been visited, otherwise false

Definition at line 39 of file Solver.hpp.

                               {
    return visited.contains(&g);
  }

solve()

virtual LinkedList<GameState *> Solver::solve ( Game &  g, GameState &  gs  )

pure virtual

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.

Implemented in HillClimbingSolver, GreedySolver, AStarSolver, DepthFirstSolver, MonteCarloSolver, and BreadthFirstSolver.

Here is the caller graph for this function:

to_string()

string Solver::to_string ( )

inline

Generates a string containing useful information from the solver run.

Returns

string representation of the state-space exploration

Definition at line 149 of file Solver.hpp.

                     {
    return string(
        "\t\t\t\tSeconds: ").append(std::to_string(getSecondsToSolve())).append(
        "\n\t\t Solution depth: ").append(
        std::to_string(getSolutionDepth())).append("\n\t Max depth explored: ").
        append(
        std::to_string(getMaxDepth())).append("\nNumber of visited nodes: ").append(
        std::to_string(getVisitedNodes())).append("\n");
  }

visit() [1/2]

LinkedList<GameState *> Solver::visit ( GameState *  current )

inlineprotected

Definition at line 43 of file Solver.hpp.

                                                    {
    return visit(current, true);
  }

Here is the call graph for this function:

visit() [2/2]

LinkedList<GameState *> Solver::visit ( GameState *  current, bool  keepVisited  )

inlineprotected

Visit a game state, adding it to the list of visited states and returning its valid child states.

Parameters

current

the state to be visited

Returns

a list of the valid child states. A valid child state is the result state of applying a valid action to the current state. Only states that have not been visited before by the solver are returned.

Definition at line 50 of file Solver.hpp.

                                                                      {
    LinkedList<GameState *> children;
    GameAction actions[4]{RIGHT, DOWN, LEFT, UP};

    // add current state to the list of visited states
    if (keepVisited)
      visited.insert(current);

    // keep a record of the maximum depth the solver has explored
    if (current->getDepth() > maxDepth) maxDepth = current->getDepth();

    // iterate through the 4 actions
    for (int i = 0; i < 4; i ++) {
      // check if the action is valid
      if (current->isValid(actions[i])) {
        // generate a child state from the valid action
        // and add it to the return list, only if the
        // child node has not been visited by the solver before
        GameState *newState = new GameState(current, actions[i]);

        if (! isVisited(*newState)) children.insert(newState);
        else delete newState;
      }
    }

    // throws an exception in case all actions give valid states,
    // since at least one state was already visited
    if (keepVisited && (children.getSize() == 4) && (current->getDepth() > 0)) {
      throw invalid_argument("Duplicate states being visited.");
    }

    return children;
  }

Here is the call graph for this function:

Field Documentation

maxDepth

int Solver::maxDepth

protected

Definition at line 30 of file Solver.hpp.

secondsToSolve

float Solver::secondsToSolve

protected

Definition at line 31 of file Solver.hpp.

solutionDepth

int Solver::solutionDepth

protected

Definition at line 30 of file Solver.hpp.

solved

bool Solver::solved

protected

Definition at line 34 of file Solver.hpp.

visited

OrderedList<GameState *> Solver::visited = OrderedList<GameState *>(compare)

protected

Definition at line 27 of file Solver.hpp.

visitedNodes

int Solver::visitedNodes

protected

Definition at line 30 of file Solver.hpp.

---

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

• include/Solver.hpp