Solving Rush Hour with Solidity (1)

Solidity, the popular smart contract programming language for Ethereum, is usually associated with complex financial applications and dApps. But what if we used its logical capabilities for something lighter – a fun puzzle game? In this post, we'll explore how to build a basic Rush Hour puzzle solver using Solidity.

Rush Hour Puzzle

Rush Hour is a sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. It is now being manufactured by ThinkFun (formerly Binary Arts).
https://www.wikiwand.com/en/Rush_Hour_(puzzle)

Let's get it work

Here is the logic optimization board that I draw. Not sure if you can understand it but anyways...
Logic Board

Encoding the park Map

One approach is to represent the entire playing field as a single uint64 which stores as 8 bytes. Each bit in the uint64 can signify a space on the grid. A value of 1 indicates a blocked space (like a fence), and 0 represents an open space (like a parking spot).

 0 0 0 0 0 0 0 0
 0 1 1 1 1 1 1 0
 0 1 1 1 1 1 1 0
 0 1 1 1 1 1 1 0
 0 1 1 1 1 1 1 0
 0 1 1 1 1 1 1 0
 0 1 1 1 1 1 1 0
 0 0 0 0 0 0 0 0

 1 1 1 1 1 1 1 1
 1 0 0 0 0 0 0 1
 1 0 0 0 0 0 0 1
 1 0 0 0 0 0 0 1
 1 0 0 0 0 0 0 1
 1 0 0 0 0 0 0 1
 1 0 0 0 0 0 0 1
 1 1 1 1 1 1 1 1

Encoding the car

Solidity doesn't have a native data type to directly represent a car with its position and orientation.

• Bit Manipulation: We can manipulate specific bits within the uint64 representing the grid to indicate the car's location and size based on its length (e.g., setting bits corresponding to the car's position).

 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 1 1 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0

Here, the car occupying position (2, 0) with a horizontal orientation and length 2 could be represented by setting the bits at positions 36 and 37 in the uint256 representing the grid. This effectively translates to 2^36 + 2^37.

Calculating Next Position

Once we have the direction encoded, we can calculate the car's next position based on its current location and the chosen direction. This involves bit shifting operations within the uint64 representing the grid.

For example:
Moving the car right from position (2, 0) (represented by 2^36 + 2^37) would involve shifting the car's bit representation by one position to the right. This translates to dividing by 2: (2^36 + 2^37) / 2 = 2^35 + 2^36.
Moving the car down eight positions would involve shifting the car's bit representation eight positions to the right. This translates to dividing by 2 raised to the power of 8: (2^36 + 2^37) / 2^8 = 2^28 + 2^29.

Collision Detection with Bitwise Operations

To check if the car's next position is occupied by another car or a fence, we can leverage bitwise operations. Here's the approach:

Exclusive OR: Perform an exclusive OR (XOR) operation between the following:

A uint256 representing the full park map with all bits set to 1 (occupied spaces).
A uint256 representing the fence with only the outer border bits set.
A uint256 representing the car's next position after the movement calculation.
Collision Check: If the result of the XOR operation is greater than 0, it indicates that at least one bit in the car's next position overlaps with either a blocked space or the fence, signifying a collision.

Packing Car Positions

One efficient way that I am using to represent the entire car configuration is to create a single uint64 that holds the bitwise representation of all cars on the grid.

Memoization - Remembering Visited Paths

To optimize the search process, I would like to introduce the concept of memoization. This technique involves storing the results of expensive function calls to avoid redundant calculations.

In the context of Rush Hour, we can:

1. Track Visited Paths: Maintain a data to store the historical positions of each car during the search process.
2. Check Before Moving: Before attempting a car movement, check the memoization data to see if the car has already occupied that position in a previous iteration.
3. Skip Redundant Moves: If the car's intended position is found in its historical paths, skip that move and explore other possibilities. This prevents revisiting already explored dead-ends, significantly reducing the search space.

Impact on Complexity

By employing memoization, the number of explored possibilities can be drastically reduced compared to a brute-force approach that tries every single move. In your example:

Brute Force: Without memoization, exploring all possible cases for a single car on a board width of n would result in 2^36 possibilities.
Memoization with Bounds: With memoization, the maximum number of explored possibilities for a car with i ID (car number i+1 on the map) and ending position at index j on the board can be estimated by:

∑((5^i)*j)

Second topic is coming

I will continue on second post