Create random puzzles for rush hour games

Question

If you are not familiar with this, the game consists of a set of cars of different sizes, installed horizontally or vertically, on an NxM grid that has one output. Each vehicle can move forward / backward in the directions in which it is installed, until another vehicle locks it. You can never change the direction of the car. There is one special car, usually red. It is installed in the same row as the exit, and the goal of the game is to find a series of moves (movement - moving the car N steps back or forward), which will allow the red car to leave the maze.

I tried to think about how to create instances of this problem, creating difficulty levels based on the minimum amount to solve this problem.

Any idea of ​​an algorithm or strategy for this?

Thanks in advance!

Answer 1

One possible approach would be to create it in reverse order.

• Create a random board that has a red car in a winning position.
• Build a chart of all reachable positions.
• Choose the position with the greatest distance from each winning position.

The number of reachable positions is not so large (probably always below 100 thousand), therefore, options (2) and (3) are possible.

How to create more complex instances using local search

It is possible that the above approach will not lead to hard cases, since most random cases do not lead to complex vehicle interactions.

You can perform a local search that requires

• way to create other boards from an existing
• rating / suitability function

(2) simple, perhaps use the length of the longest solution, see above. Although it is quite expensive.

(1) requires some thought. Possible changes:

• add a car somewhere
• remove the car (I assume this will always make the board easier).

These two are enough to cover all possible boards. But you can add other methods, since removal makes the board easier. Here are some ideas:

• move the car perpendicular to its direction of movement
• exchange cars in one lane (aaa..bb.) -> (bb..aaa.)

Hillclimbing / sceepest ascend is probably bad due to a large branching factor. You can try to query a set of possible neighboring boards, i.e. Do not look at everything, but only at a few random ones.

Answer 2

The board asked in the question has no more than 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 computers. So a possible approach would be to

• plot all positions (nodes represent positions, edges move),
• find the number of winning moves for all nodes (for example, using Dijkstra ) and
• select node far away from the target.

Answer 3

I know this is ancient, but I recently had to deal with a similar problem, so maybe this could help.

• Building instances by applying random operators from a terminal state (i.e. the opposite) will not work. This is due to symmetry in the state space. On average, you find yourself in a state that is too close to the state of the terminal.

• Instead, it was best to generate the initial states (by placing random machines in the grid), and then try to solve it using some algorithm with a limited heuristic search, such as IDA * or branches and borders. If the instance cannot be resolved within the constraint, discard it.

• Try to avoid A *. If you have a definition of what you mean, this is a “hard” instance (I think 16 moves are pretty complicated) you can use A * with a trim rule that prevents x nodes from expanding with g (x) + h (x)> T (T is your threshold (e.g. 16)).

• Heuristic function . Since you do not need to be optimal in solving it, you can use any simple invalid heuristic, such as the number of squared obstacles for the target. Alternatively, if you need a more efficient heuristic function, you can implement the distance function in Manhattan by generating the entire set of win states for the generated puzzle, and then using the minimum distance from the current state to any terminal state.