Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

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< Hashm_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, CacheEntrym_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:
Generated at Sun Jan 6 18:49:12 2002 for EasySok by doxygen1.2.9.1 written by Dimitri van Heesch, © 1997-2001