Rush Hour Backtracking Algorithm

In this challenge we will implement a backtracking algorithm to solve a game of Rush Hour using a trial and error approach. We will also investigate the need to apply some basic heuristics to improve our algorithm and avoid a situation of stack overflow, a common issue with recursive/backtracking algorithms when there are too many paths to investigate!

First, you will need to be familiar with the rules of the Rush Hour game. You can find out more about this game on this page.

The goal of the game is to get the red car out of the parking bay through the exit of the board (on the right hand side of the 6×6 board). To do so the player has to move the other vehicles out of its way by sliding them either vertically or horizontally depending on the orientation of the vehicle. The vehicles of different colours and length (cars are 2 squares long and trucks are three squares long) are set up at the start of the game based on a given configuration). In the physical game, there are 40 different initial configurations to solve. The 40 configurations are categorised in 4 grouped based on their difficulty level: the number of moves needed to solve the puzzle. The 4 categories are: Beginner Level, Intermediate, Advanced and Expert Level!

To implement this game, we are using a 2D array/grid to represent the parking bay with all the vehicles. Each number on this array represent the colour of a vehicle. On this grid/array:

• An empty square has a value 0,
• The bordering walls have a value of 1.
• The red car has a value of 2.
• All the other colours/vehicles have a value between 3 and 14.

A backtracking algorithm is a recursive algorithm that will test potentially every possible move, one by one. To reduce the number of possibilities, a backtracking algorithm will aim to identify as soon as possible, when a move can be discarded as it will not lead to a solution. (Without the need to investigate different moves to complete the puzzle, hence saving some processing time!).

Backtracking algorithms, being recursive use a “call stack” to record/memorise the state of the variables and data structures used in the recursive function for each move in order to be able to reload them when backtracking. In this case the full copy of the 2D grid will be pushed to a the call stack for each move/call of the recursive function. Such an algorithm is hence fairly greedy in terms of system resources and when there are too many moves to investigate before reaching a solution, the code may generate a stack overflow error which would stop the execution of the code before finding a solution!

One approach to make a backtracking algorithm more effective is to apply some heuristics in the implementation of the game to try to focus first on the moves which are more likely to lead towards a solution. Our second approach is applying some basic heuristics based on the following assumptions:

• If the red car can slide to the right, this should be the first move to make as it will bring the car closer to the exit gate so may be more likely to lead to a solution in less steps. (though this is not always the case, especially with “expert level” challenges)
• If the red car cannot be moved to the right, the algorithm should focus on sliding other horizontal cars/trucks to the left (when possible), as this would free up spaces on the right of the grid, which could be needed to then slide vertical cars that may be obstructing the exit gate.
• Then, the first set of vehicles to focus on are the vertical cars/trucks which are blocking the path for the red car to reach the exit gate. When possible these should be moved up or down. Trucks (which are 3 square long) should preferably moved down as if they are not parked alongside the bottom edge of the grid, they will block the path of the red car.

Python Implementation