C# implementation for Rush Hour puzzle

 
This project focuses on Rush Hour puzzle such as the following:



In Rush Hour puzzle, the red car is stuck in traffic and is trying to escape. Cars can be moved up and down or left and right. They are allowed to move more than one square in a single move, but cannot move over or through other cars. The goal is to clear a path so that the red car can escape past the yellow arrow.

A* and heuristics for Rush Hour

One of the main parts of this project is implementing A* and three heuristics for solving Rush Hour puzzles. Our implementation of A* should check to be sure that it is not re-exploring parts of the search space that have already been explored. The goal of the search is to solve the puzzle in the fewest moves possible, so the cost of a search path should simply be the number of legal moves made.
Here are the three heuristics that we should implement and test A* on:

1. The trivial zero heuristic whose value is equal to zero in all states. Note that using A* with this heuristic is equivalent to breadth-first search.


2. The blocking heuristic which is equal to zero at any goal state, and is equal to one plus the number of cars blocking the path to the exit in all other states. For instance, in the state above, there are two cars (namely, the two green ones) on the path between the red car and the exit. Therefore, in this state, the blocking heuristic would be equal to three.


3. A third, advanced heuristic of our own choosing and invention. We should aim for a heuristic that will be at least as effective as the blocking heuristic. A trivial heuristic, comparable to the zero heuristic in triviality, would not be appropriate.

Note that every car is constrained to only move horizontally or vertically. Therefore, each car has one dimension along which it is fixed, and another dimension along which it can be moved.
Our A* implementation will take as input a heuristic (1-3) and a string representing the names of the text file containing the initial state.

The output should contain:

1. the solution as a sequence of operations; for example:
Move car # 3 down 3 squares
Move car # 1 down 1 square

2. The depth of the goal state found
3. The number of nodes expanded
4. The branching factor
5. The cost of the solution found

Locations on the grid of a Rush Hour puzzle are identified by their (x, y) coordinates, where the upper left corner is square (0,0). For instance, in the puzzle above, the red car occupies squares (1,2) and (2,2). The goal is to move the red car so that it occupies squares (5,2) and (6,2).
The goal car (the one we are trying to move to the exit) is always assigned index 0. The remaining cars are indexed 1,2,4, …
Puzzles should be read from a file into memory and they must be encoded as in the following example representing the puzzle above:

6
0 1 2 h 2
1 2 0 v 2
2 4 0 h 2
3 3 1 v 3
4 4 1 v 2
5 4 3 h 2


The first line "6", gives the size of the grid, i.e., this puzzle is defined on a 6x6 grid. The next line, "0 1 2 h 2", gives a description of the red car. The first number is the car ID. The second two numbers (1,2) give the (x, y) coordinates of the upper left corner of the car. The "h" indicates that the car is horizontally oriented ("v" would have indicated vertical orientation). The last number "2" indicates that the car has size (i.e., length) 2. The next line, "1 2 0 v 2" describes the pink car, and so on.


For this Project , we can assume that the puzzle is a 6x6 grid, that the goal car always horizontally oriented.
We may notice that the results we achieve for the number of nodes searched are different, and frequently better, than the sample ones above. The number of nodes searched can vary pretty widely, even among "correct" implementations, due to slight variations involving the handling of nodes in the fringe that have the same cost. The results above were achieved for an implementation in which such ties are broken in a FIFO order, i.e., the node that was placed in the OPEN earliest is removed first, an approach that actually appears to be suboptimal. In any case, any way we choose to handle ties is acceptable and the potential variation in results will be taken into account when grading our project. (However, see the note below under "debugging tips".)

 

Abed El-Azeem Bukhari

abedbukhari[at]hotmail[dot]com

Last edited Mar 16, 2013 at 6:51 PM by AbedBukhari, version 6