If you like this project please consider giving it a ⭐ star ⭐. Thanks!
The goal of this project is to build a generic interactive pluggable application for solving puzzles (i.e. 8-puzzle, 15-puzzle,
n-queens, Sudoku, graph-coloring etc.) using different problem-solving techniques (i.e. informed search, uninformed search, hill-climbing search etc.).
Here by word pluggable we mean in solving puzzles user can independently decide the search strategy along with the
custom heuristic functions. If needed, user can extend this project to device their own solution with a very low effort.
Besides, this application is designed in a way that, it will be an easy-going platform for benchmarking any puzzles w.r.t. different
state space search strategy, optimization techniques and heuristic functions.
The project has several independent parts that we combine to work as a whole. Directory "core" contains two factory
methods that produce the puzzle solver and heuristic instance based on the parameter passed. Puzzle solutions can be
implemented in separate directory as we have done for 8-puzzle,
n-queens,
and k-coloring here. Heuristic implementations
placed in the heuristic sub-directory under the corresponding puzzle. Directory "utils" all the utility methods that
help other functions to operate.
Please keep in mind, this is an active project and project architecture may change without any prior announcement. But all the future updates will be maintained in a way so that the project integrity will ke kept, meaning you will not face any difficulty in building or running the project.
# go to project directory
$ cd puzzle-solver
# build the project
$ make clean && make
General run command:
./puzzle -problem {PUZZLE_NAME} \
-algo {ALGORITHM_NAME} -mode {MODE} \
-heu {HEURISTIC_METHOD} \
-initial {INITIAL_STATE_OF_THE_GAME} -goal {GOAL_STATE_OF_THE_GAME} \
-board_dim {DIMENSION_OF_THE_BOARD} -mx_sideways_move {MAX_SIDEWAYS_MOVE}\
-print_path {PRINT_INITIAL_TO_GOAL}
Here is the parameter definition,
- -problem: Specify the puzzle name to solve, for example,
8-puzzle. - -algo: Specify the search strategy to solve the puzzle, for example, "A*", "bfs", "dfs", etc.
- -mode: Specify the inner methodology for the search strategy, for example, "bi-directional" bfs, "stack-based" dfs, etc.
- -heuristic: Specify the heuristic function you want to use, for example, "hamming", "manhattan", "euclidean", etc. [default: manhattan]
- -initial: Specify the initial board setup for your puzzle
- -goal: Specify the goal state of your puzzle
- -board_dim: Board dimension, may use representing any square board
- -mx_sideways_move: Maximum allowed sideways move in hill-climbing search
- -print_path: Flag to indicate printing path if solution exist, accepts boolean string, i.e., "true" or "false".
- -file: Input file containing large input data. For example, we keep the constraint graph needed by
k-coloringalgorithm. - -mcolor: Maximum allowed color, value -1 means we need to find the chromatic number, value (>0) means we need to color the graph by using this number of colors.
- -mrv: Flag to indicate whether we will apply heuristic Minimum Remaining Values (MRV) for selecting the next vertex to color.
- -degree_heu: Flag to indicate whether we will apply heuristic Minimum Remaining Values (MRV) for selecting the next vertex to color.
- -lcv: Flag to indicate whether we will apply heuristic Minimum Remaining Values (MRV) for selecting the next vertex to color.
While implementing different algorithms for solving 8-puzzle problem, we found some optimization techniques help the algorithms'
to be more efficient. These techniques can be rigid or independent w.r.t. the algorithm itself.
For example, bi-directional search technique is very common in the domain of searching algorithms and can be applied to
a large number of algorithms. Bi-directional search launch two searches, one from the initial state to the goal state
and another one from the reverse direction. The key benefit here is it help reduce the search space, as we know the
search trees grow exponentially by their depth. From table 1, we can find that the bi-directional strategy generates at least 2x
less nodes comparing to the original algorithms (i.e. Optimized BFS vs. Bi-directional BFS). Fig 1 give a brief idea about the
state space reduction by bi-directional strategy while applied in BFS. We can also observe in some cases within some constraints
the original algorithm fails to reach the goal, whereas applying bi-directional approach may help reaching the goal (i.e.
DLS vs. Bi-directional DLS for input 5). This become possible due to the lower search space generated by bi-directional approaches.
|
| Figure 1: Showing search space reduction by bi-directional search |
Some techniques can be applied to very selective algorithms. For example, DFS is a very well known algorithm in the domain of state space search and can be implemented in recursive and non-recursive (stack based) way. The benefit of using stack based DFS is avoiding stack overflow due to excessively deep recursions.
H.E. Lehtihet's reply in [3]
Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at
hand and they try to take full advantage of the particularities of this problem. However, because
they are often too greedy, they usually get trapped in a local optimum and thus fail, in general,
to obtain the global optimum solution.
Meta-heuristics, on the other hand, are problem-independent techniques. As such, they do not take
advantage of any specificity of the problem and, therefore, can be used as black boxes. In general,
they are not greedy. In fact, they may even accept a temporary deterioration of the solution (see
for example, the simulated-annealing technique), which allows them to explore more thoroughly the
solution space and thus to get a hopefully better solution (that sometimes will coincide with the
global optimum). Please note that although a meta-heuristic is a problem-independent technique,
it is nonetheless necessary to do some fine-tuning of its intrinsic parameters in order to adapt
the technique to the problem at hand.
You might want to take a look also at the so-called hyper-heuristics that go a step beyond
meta-heuristics. The particularity of hyper-heuristics is that their search space is not the
usual space of the solutions but is rather the space of heuristics or meta-heuristics. Indeed,
hyper-heuristics can be viewed as "heuristics to search for heuristics". There is also a slightly
different category defined as "heuristics to generate heuristics".
- Will solve 8-queen puzzle by different non-classical search strategy.
- Will solve 2 player game by applying minimax decisions and α–β pruning.
- Found several puzzles that can be tried later
- Solving Sudoku with Ant Colony Optimization
- [Blog] Problem Solving Techniques part1: https://mhesham.wordpress.com/2010/04/08/problem-solving-techniques-part1/
- [Blog] Problem Solving Techniques part2: https://mhesham.wordpress.com/tag/depth-limited-search/
- [ResearchGate] What are the differences between heuristics and metaheuristics? https://www.researchgate.net/post/What_are_the_differences_between_heuristics_and_metaheuristics
- [Paper] A Comparison between Heuristic and Meta- Heuristic Methods for Solving the Multiple Traveling Salesman Problem: https://publications.waset.org/4699/a-comparison-between-heuristic-and-meta-heuristic-methods-for-solving-the-multiple-traveling-salesman-problem
- [Online Book] Clever Algorithms: Nature-Inspired Programming Recipes: www.cleveralgorithms.com/nature-inspired/index.html