Deliverables 1 – Dijkstra Solver Source Code
You are expected to hand in the source code for your solver, written in C. Obviously, your
source code is expected to compile and execute flawlessly using the following makefile
command: make generating an executable called sokoban. Remember to compile using the
optimization flag gcc -03 for doing your experiments, it will run twice as quickly as compiling
with the debugging flag gcc -g (see Makefile, and change the CC variable accordingly). For
the submission, please submit your makefile with gcc -g option, as our scripts need this
flag for testing. Your program must not be compiled under any flags that prevents it from
working under gdb or valgrind.
Your implementation should work well over the first 3 layouts, but it will not be expected to
find a solution to any layout, as it may exceed the available RAM in your computer before
finding a solution. Feel free to explore maps given in the folder maps_suites. They are taken
from the official benchmarks of sokoban. All you have to do is to copy and paste a single
map into a new file, and then call it with your solver.
Deadlock Detection (Optimization)
The simplest way to improve the code is by improving the deadlock detection implemented
(SimpleCornerDeadlock) in Algorithm 1-line 18. You can find the C implementation inside
utils.c:235. Implement at least 1 deadlock detection in the link above.
Take a look at these 2 links for further optimization ideas & insights.
If you do any optimizations & changes to the Data Structures & deadlock detection
improvement, please make sure to explain concisely what it is that you implemented, why
you chose that optimization, how it affects the performance (show number of expanded
nodes before and after the optimization for a set of test maps), and where the code of the
optimizations is located. This explanation should be included in the file located at the root of
the basecode: README.md. Please make sure that your solver still returns the optimal
solution.
Rubric
Assignment marks will be divided into three different components.
1) Solver(12)
? Finds solution for the capability test cases (10)
? No memory error (1)
? No memory leak (1)
2) Code Style (2)
3) Optimization (1)
Please note that you should be ready to answer any question we might have on the
details of your assignment solution by e-mail, or even attending a brief interview with
me, in order to clarify any doubts we might have.
? For this please give me a detailed summarization to the code implemented. How,
why and what you implemented and how and what else could you have implemented
instead.
Maps & Solution formats
Puzzle File Format
We adapted the sokoban file reader to support the following specification, but we don’t
support comments specified by %.
Deliverables 1 – Dijkstra Solver Source Code You are expected to hand in the source code for your solver, written in C. Obviously, your source code is expected to compile and execute flawlessly