A rush hour solver in Haskell. In collaboration with @sanantoniochili

The programme rush_hour.hs is an implementation in Haskell of a solver for the classic puzzle game rush hour. There are two main solvers implemented by the functions solve and solve_astar. The function solve implements a simple Bridth First Search, while solve_astar uses a heuristic described here.

The input of the solve functions is an initial state of the rush hour grid. Although a grid state is encoded internally differently, there are provided the functions readState and writeState to convert a simple string in a valid grid state. An example of such a valid state-string is given bellow.

"...a\n==.a\n....\n....\n"  

which describes the following state:

...a  
==.a  
....  
....  

The blocking cars are represented with the same character (e.g. 'a'), the red car, is represented by the character '=' and the empty places are represented by '.'. Calling the function solve (readState "...a\n==.a\n....\n....\n") in GHCi prompt, will return a list of moves in order to the red car, be unblocked. For a more user friendly list of subsequent string-states to be printed, you may use the function printSolution, see the examples bellow.

> state = readState "...a\n==.a\n....\n....\n"
> printSolution state (solve state)

...a
==.a
....
....

....
==..
...a
...a

....
..==
...a
...a

> state = readState "..abbb\n..a.c.\n..==c.\n....d.\n....d.\n....d.\n"
> printSolution state (solve_astar state)

..abbb
..a.c.
..==c.
....d.
....d.
....d.

..abbb
..a.c.
==..c.
....d.
....d.
....d.

...bbb
....c.
==..c.
....d.
..a.d.
..a.d.

.bbb..
....c.
==..c.
....d.
..a.d.
..a.d.

.bbbc.
....c.
==....
....d.
..a.d.
..a.d.

.bbbc.
....c.
....==
....d.
..a.d.
..a.d.

The file rush_hour.pdf contains a detailed description of the assignment's requirements (in Greek), while in README.pdf we describe in detail the implementation (in Greek).

If a sting-state is given to solve (or solve_astar), where there is no solution, the function will not terminate.