---

Solver Class Reference

Used for solving a map. More...

#include <solver.h>

List of all members.

Public Methods
	Solver (Map const &map, int cache_size)
bool	prepare ()
bool	solve (int steps)
int	depth () const
int	actMinDepth () const
int	actMaxDepth () const
int	maxDepthReached () const
int	maxDepth () const
int	nextMaxDepth () const
double	percentageCompleted () const
Movements	moves () const
Movements	bestEffort () const
Private Types
enum	PatternType {   KEEPER = 1 << 0, KEEPER_ON_GOAL = 1 << 1, GEM = 1 << 2, GEM_ON_GOAL = 1 << 3,   EMPTY = 1 << 4, GOAL = 1 << 5, WALL = 1 << 6, OUTSIDE = 1 << 7 }
Private Methods
bool	doSingleStep ()
bool	startSearch ()
bool	collapse ()
void	expand ()
bool	processEndNodes ()
std::vector< int > const &	validMoves () const
int	movesForGem (int keeper_pos, int gem_pos, int goal_pos) const
bool	isDeadlock (int position, bool ignore_on_goal=false) const
int	minMovesForSolution (int moved_gem_pos) const
int	assignmentSolver (std::vector< int > &matrix, int dim) const
int	lowerBound (Hash const &hash, int moved_gem_pos, int depth)
void	updateCache (Hash const &hash, int moves_to_solve, int depth)
void	insertInCache (Hash const &hash, int moves_to_solve, int depth, bool calculated)
void	setupCache ()
std::vector< int >	getGemPositions (Map const &map) const
void	setupDistanceMap ()
void	setupDeadlockPatterns ()
Movements	getFullMoves () const
Private Attributes
Map	m_map
Map	m_start_map
Map	m_empty_map
std::vector< int >	m_pos
std::vector< int >	m_move_lengths
std::vector< int >	m_move_offsets
std::vector< int >	m_min_solve_moves
std::vector< int >	m_moves
std::vector< int >	m_gem_positions
Movements	m_solution_moves
Movements	m_best_effort
int	m_best_effort_max_depth
int	m_best_effort_lower_bound
std::vector< int >	m_possible_gem_positions
std::vector< int >	m_goal_positions
std::vector< Hash >	m_hashs
int	m_goals
int	m_depth
int	m_act_min_depth
int	m_act_max_depth
int	m_max_depth_reached
int	m_max_depth
int const	m_width
int const	m_height
int const	m_size
int	m_xy_offsets [4]
int	m_min_add_depth
bool	m_solution_possible
std::map< Hash, CacheEntry >	m_cache
int	m_max_cache_size
int	m_cache_size
std::vector< int >	m_depth_counts
int	m_max_depth_counts
std::vector< int >	m_distance_map
std::vector< Q_UINT32 >	m_reachable_map
int	m_reachable_map_gem
bool	m_solve_finished
std::vector< int >	m_deadlock_patterns
std::vector< int >	m_deadlock_pattern_positions
std::vector< int >	m_deadlock_pattern_lengths
Static Private Attributes
int const	s_unsolvable

---

Detailed Description

Used for solving a map.

Uses IDA* and some simple enhancements.

Author:

Ralf Schmelter (ralfs@pc2a.chemie.uni-dortmund.de).

Version:

0.1

---

Member Enumeration Documentation

enum Solver::PatternType [private]

Used to define the patterns.

---

Constructor & Destructor Documentation

Solver::Solver (  Map const & map, int cache_size )

Constructs the solver for the given map. Parameters: map   The map to solve. cache_size   The number of map hashs to put in the cache.

---

Member Function Documentation

int Solver::actMaxDepth (  )  const

Returns the actual max depth for the last call to solve().

int Solver::actMinDepth (  )  const

Returns the actual min depth for the last call to solve().

int Solver::assignmentSolver (  std::vector< int > & matrix, int dim )  const [private]

Utility function used to find the minimum number of moves.

Movements Solver::bestEffort (  )  const

Returns the moves of the best current effort.

bool Solver::collapse (  )  [private]

Callapses to an old depth.

int Solver::depth (  )  const

Returns the actual search depth.

bool Solver::doSingleStep (  )  [private]

Makes a single solve step. Returns: True, if the map is solved (the movements are then stored in m_solution_moves) or is proved to be unsolvable.

void Solver::expand (  )  [private]

Expands to a new depth.

Movements Solver::getFullMoves (  )  const [private]

Returns the movements (including keeper moves) to get to the current map.

std::vector<int> Solver::getGemPositions (  Map const & map )  const [private]

Returns a vector holding the positions (sorted) of all gems. Parameters: map   The map to use.

void Solver::insertInCache (  Hash const & hash, int moves_to_solve, int depth, bool calculated )  [private]

Inserts the given entry in the cache and removes som elements of the cache if it is full. Parameters: hash   The hash value of the map. moves_to_solve   The minimum number of moves to solve. If the value is negative, the entries is considered to be calculatable. depth   The depth of the search tree where we are. calculated   If true, the number of moves is calculated.

bool Solver::isDeadlock (  int position, bool ignore_on_goal = false )  const [private]

Returns true, if the gem at the given position is deadlocked. Parameters: map   The map to use. position   The position of the gem. ignore_on_goal   If true, we count the gem as deadlocked even if it is on a goal.

int Solver::lowerBound (  Hash const & hash, int moved_gem_pos, int depth )  [private]

Returns the lower bound for the map. Uses the cache to get better results. Parameters: map   The map to use. hash   The hash of the map. moved_gem_pos   The end position of the last moved gem. depth   The depth of the search tree where we are.

int Solver::maxDepth (  )  const

Returns the actual maximum search depth.

int Solver::maxDepthReached (  )  const

Returns the max search depth reached.

int Solver::minMovesForSolution (  int moved_gem_pos )  const [private]

Returns the minimum number of atomic gem moves to solve a map. If there are no possible moves, we return -1. Parameters: map   The map to use. moved_gem_pos   The end position of the last moved gem.

Movements Solver::moves (  )  const

Returns the moves of the solution or and empty move list if it is not solvable.

int Solver::movesForGem (  int keeper_pos, int gem_pos, int goal_pos )  const [private]

Returns the minimum number of moves to move a gem from pos1 to pos2. If there is no way from pos1 to pos2 the return -1. Parameters: keeper_pos   The position of the keeper. gem_pos   The start position of the gem as an index in m_gem_positions. goal_pos   The end position of the goal as an index in m_goal_positions.

int Solver::nextMaxDepth (  )  const

Returns the next max depth for the next iteration.

double Solver::percentageCompleted (  )  const

Returns the percentage (0 to 100) of the work in the actual iteration completed.

bool Solver::prepare (  )

Sets up the solver. You need to call this function as long as it does not returns true.

bool Solver::processEndNodes (  )  [private]

Searche the end nodes. Returns: True, if an solution was found.

void Solver::setupCache (  )  [private]

Updates the cache after starting a new search.

void Solver::setupDeadlockPatterns (  )  [private]

Sets up the deadlock patterns.

void Solver::setupDistanceMap (  )  [private]

Sets up the distance map.

bool Solver::solve (  int steps )

Tries to solve the map. You need to call this function as long as it does not returns true. Parameters: steps   The maximum number of steps to try. Returns: true If a solution or the proof of unsolvability could be found in the number of steps.

bool Solver::startSearch (  )  [private]

Starts the search with a new limit. Returns: True, if no solution could be found.

void Solver::updateCache (  Hash const & hash, int moves_to_solve, int depth )  [private]

Updates the cache entry for the given map. Parameters: hash   The hash of the map. moves_to_solve   The minimum number of moves to solve. This entry will be updated, if it is greater than the previous value. depth   The depth of the search tree where we are.

std::vector<int> const& Solver::validMoves (  )  const [private]

Returns the valid moves (menaing movements of gems) in compressed format .

---

Member Data Documentation

int Solver::m_act_max_depth [private]

The actual max depth in the last call to solve.

int Solver::m_act_min_depth [private]

The actual min depth in the last call to solve.

Movements Solver::m_best_effort [private]

The best effort moves.

int Solver::m_best_effort_lower_bound [private]

The min lower bound for the best effort.

int Solver::m_best_effort_max_depth [private]

The max depth for the best effort.

std::map<Hash, CacheEntry> Solver::m_cache [private]

The map used to find cycles in the move graph.

int Solver::m_cache_size [private]

The actual cache size.

std::vector<int> Solver::m_deadlock_pattern_lengths [private]

Here we store the length of the patterns.

std::vector<int> Solver::m_deadlock_pattern_positions [private]

Here we store the deadlock pattern positions.

std::vector<int> Solver::m_deadlock_patterns [private]

Here we store the deadlock patterns.

int Solver::m_depth [private]

The actual depth.

std::vector<int> Solver::m_depth_counts [private]

Here we store the number of entries of a given depth.

std::vector<int> Solver::m_distance_map [private]

Here we store the distance map.

Map Solver::m_empty_map [private]

The start map without gems, goals and keeper.

std::vector<int> Solver::m_gem_positions [private]

The actual positions of the gems.

std::vector<int> Solver::m_goal_positions [private]

Here we store the indices of positions with a goal.

int Solver::m_goals [private]

The number of goals.

std::vector<Hash> Solver::m_hashs [private]

Here we store the hashs for the maps.

int const Solver::m_height [private]

The height of the map.

Map Solver::m_map [private]

The act map.

int Solver::m_max_cache_size [private]

The maximum cache size.

int Solver::m_max_depth [private]

The actual max depth.

int Solver::m_max_depth_counts [private]

Here we store the max depth for m_depth_counts.

int Solver::m_max_depth_reached [private]

The maximum depth reached.

int Solver::m_min_add_depth [private]

The current mimimum distance to a solution at the current depth.

std::vector<int> Solver::m_min_solve_moves [private]

The minimum moves to solve the map.

std::vector<int> Solver::m_move_lengths [private]

The movement lengths.

std::vector<int> Solver::m_move_offsets [private]

The move offsets.

std::vector<int> Solver::m_moves [private]

The valid moves in a compressed format.

std::vector<int> Solver::m_pos [private]

The move positions.

std::vector<int> Solver::m_possible_gem_positions [private]

Here we store the indices of positions where a moveable gem might reside.

std::vector<Q_UINT32> Solver::m_reachable_map [private]

Here we store the the reachable fields for gems.

int Solver::m_reachable_map_gem [private]

Here we store the current index of the gem position for which we calc the reachable map.

int const Solver::m_size [private]

m_width * m_height.

Movements Solver::m_solution_moves [private]

The solution moves.

bool Solver::m_solution_possible [private]

True, if at least one move seems to lead to a solution.

bool Solver::m_solve_finished [private]

If true, no further calls ot solve are needed.

Map Solver::m_start_map [private]

The start map.

int const Solver::m_width [private]

The width of the map.

int Solver::m_xy_offsets[4] [private]

The offsets for atomic moves.

int const Solver::s_unsolvable [static, private]

The number of pushes for unsolvable positions.

---

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

• solver.h

---