BreadthFirstSolver Class Reference

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

#include <BreadthFirstSolver.hpp>

Inheritance diagram for BreadthFirstSolver:

Collaboration diagram for BreadthFirstSolver:

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

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 breadth-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 breadth-first search strategy

Definition at line 14 of file BreadthFirstSolver.hpp.

Member Function Documentation

solve()

LinkedList<GameState *> BreadthFirstSolver::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 17 of file BreadthFirstSolver.hpp.

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

    const clock_t start = clock();
    expanded.enqueue(&g0);

    int currentDepth = 0;

    cout << "Depth\tVisited\t\tExpanded\n";
    while (! expanded.isEmpty()) {
      GameState *currentGame = expanded.dequeue();

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

      // if new depth, output a line to stdout
      if (currentGame->getDepth() != currentDepth) {
        currentDepth = currentGame->getDepth();
        cout << currentGame->getDepth() << "\t\t" << visited.getSize() << "\t\t\t" << expanded.getSize() << endl;
      }

      //expand children
      LinkedList<GameState *> children = visit(currentGame);
      while (! children.isEmpty()) expanded.enqueue(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:

---

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

• include/BreadthFirstSolver.hpp