Background
Safari Rush Hour is a variation on the popular Rush Hour game from Binary Arts. The object is to move your car through a tangle of obstacles to reach the exit. Your job is to write a program to find the best way out of the traffic.
Rules
Safari Rush Hour is played on a 7 x 7 game grid with up to 19 playing pieces (safari rover and animals). The object is to slide the safari rover through the exit gate in the playing grid frame. Each puzzle gives a configuration of animals and the safari rover. To play, you shift the animals and safari rover up, down, left, and right until the path is clear to make your escape. Note: lions, lionesses, impalas, zebras, rhinos, and elephants move only forward and reverse. The large square safari rover and the wild dogs (termite mound) may move up, down, right, and left. No lifting of playing pieces off of the gameboard grid surface once play has begun.
Example
The predecessor game of Safari Rush Hour is Rush Hour. It is played on a smaller board, with a different number and different shaped pieces. Try playing the applet here. You can practice on this applet to get an idea of how to solve Safari Rush Hour puzzles.
Input
A sample problem input looks as follows:1
2
3
4
5
6
7
8P J1
.......
.rrrf..
hh..fq.!
o.xx.q.!
o.xx.q.
ob..ee.
.bppp..
The first line indicates a problem (“P”) and the name of the problem (“J1”). The problems are all numbered, and the first letter indicates the difficulty of the problem: “J” is junior, “B” is beginner, “I” is intermediate, “A” is advanced, and “E” is expert. In the puzzle specification, the letters stand for the playing pieces: 2x2 pieces: termite mounds (u,v) and safari rover (x); 3x1 pieces: elephant (o, q, s) and rhino (p, r); 2x1 pieces: lion (a, f), lioness (d, g, j), impala (b, h, i, k) and zebra (c, e). The actual names do not matter; all that is important is the shape of each of the pieces and the way that they move. The “!” indicates the exit (the exit position is fixed and does not change from puzzle to puzzle).
Solution
Using A or IDA, your request is to solve a given puzzle in the minimum number of moves with the smallest search tree possible. The latter implies enhancing A/IDA to eliminate as much of the search tree as possible using some of the standard techniques in the literature (or possibly some of your own application-dependent enhancements). Files a2-orig.data, a2-deep.data, a2-vast.data, a2-fiendish.data contain test sets of problems for evaluating your solutions.
Report solution using the following format:1
solution [id] [t] [n] [move_1] ... [move_n]
where [id] is the problem id, [t] is the wallclock time in seconds your program required to find the solution (or “timeout” if your program timed out - see -t options below) [n] is the number of moves and [move_i] is a move encoded by specifying the name of the piece, its move direction (“l”eft, “r”ight, “u”p, or “d”own) followed by the number of squares that the piece moves. For example, a solution line for the puzzle above is:1
solution J1 0.15 5 el1 qd2 fu1 xu1 xr5
The length of a solution is the number of move strings. Note that the rover must be moved off the board completely. Test your program on the junior/beginner problems. Then work your way up to the more difficult ones.
Your program should output the following. For each input problem, I want to see statistics on the number of nodes searched, execution time, average h-value for all nodes where an evaluation occurred in the tree, and min/average/max depth of nodes where a cutoff occurred. When the program successfully terminates, print out the solution.
Specifications
Your program should take input from stdin and output to stdout. The input is in the format given above possibly containing multiple positions which need to be solved by your program in turn.
You program must be single-threaded and use no more than 200 MB of RAM. You must implement command-line option -t n, where n is an integer. This option sets the program to stop searching a position after n seconds of real time. If a timeout occurs your program must report “timeout” as time and proceed with the next problem.
Submission
A tar file that contains your source code, a makefile, and a report in pdf format. Your executable must be named safari. Late requests will not be accepted!
In the report, give me a description of your program. Skip the basics (such as A/IDA). I want to know any search enhancements that you tried. Describe your heuristic function. Tell me what you did that was interesting. What problems did you encounter? How can your solution be improved? This document must be no longer than five pages. Include a table of experimental results that shows the (positive?) impact of your enhancements.