---

solver.h

/*
 *   EasySok --- A(nother) sokoban game for KDE.
 *
 *   Copyright (C) 2001 by Ralf Schmelter (ralfs@pc2a.chemie.uni-dortmund.de).
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License version 2 as
 *   published by the Free Software Foundation.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */


#ifndef EASYSOK_SOLVER_INC_GUARD_H
#define EASYSOK_SOLVER_INC_GUARD_H


#include <map>
#include <utility>
#include <vector>

#include "hash.h"
#include "map.h"
#include "move.h"
#include "movements.h"




class Solver
{

public:

    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:

    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;


    class CacheEntry
    {

    public:

        CacheEntry(int moves_to_solve, int depth, bool calculated);


        int movesToSolve() const;


        bool unsolvable() const;


        void setMovesToSolve(int moves_to_solve);


        int depth() const;


        void setDepth(int new_depth);


        bool wasCalculated() const;


        bool wasTouched() const;


        void touch();


        void untouch();


    private:

        Q_UINT32 m_data;
    };


    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;


    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
    };


    std::vector<int> m_deadlock_patterns;


    std::vector<int> m_deadlock_pattern_positions;


    std::vector<int> m_deadlock_pattern_lengths;


    static int const s_unsolvable;
};


#endif

---