Generating Random Puzzle Boards for Rush Hour Game

Question

If you're not familiar with it, the game consists of a collection of cars of varying sizes, set either horizontally or vertically, on an NxM grid that has a single exit. Each car can move forward/backward in the directions it's set in, as long as another car is not blocking it. You can never change the direction of a car. There is one special car, usually, it's the red one. It's set in the same row that the exit is in, and the objective of the game is to find a series of moves (a move - moving a car N steps back or forward) that will allow the red car to drive out of the maze.

I've been trying to think about how to generate instances for this problem, generating levels of difficulty based on the minimum number to solve the board.

Any idea of an algorithm or a strategy to do that?

Thanks in advance!

Answer 1

Rush Hour is a board of size M x N. The board is full of cars and trucks. Every car has size 1x2 and each truck has a size 1x3. Cars and trucks can be both horizontal or vertical. At every step, we can move a horizontal car or truck along its row if there are no other objects in its way. Thus, we can move a vertical car or truck along its column. Among the cars, one relates to the president. It is always horizontal. The game intends to get the president's car to the exit gate at the rightmost column in its row. You need to write a solver for Rush Hour, which takes a map of the game and returns the minimum number of steps to solve it. 

The board given in the question has at most 4*4*4*5*5*3*5 = 24.000 possible configurations, given the placement of cars.

A graph with 24.000 nodes is not very large for today's systems. So a desirable way would be to

• create the graph of all positions (nodes are positions, edges are moves)

• find the number of winning moves for all nodes (e.g. using Dijkstra)

• pick a node with a large distance from the goal.