Solving Rush Hour with Solidity (1)

Jenson — Tue, 26 Mar 2024 19:48:19 +0000

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:

Track Visited Paths: Maintain a data to store the historical positions of each car during the search process.
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.
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

Memory Mapping for Rush Hour in Solidity (A Novel Approach)

Jenson — Fri, 22 Mar 2024 09:49:51 +0000

I approached solving Rush Hour puzzles using Solidity's core data structures and logic capabilities. Now, let's dive into a more experimental approach that leverages memory mapping for potential performance gains.

Memory Allocation based on Car Count

The core idea is to pre-allocate memory during board initialization. The total memory size is calculated based on the number of cars (cars) on the board. Here's the logic:

Exponential Growth: We assume each car can have up to five different positions/orientations (considering up, down, left, right, and no movement).
Total Cases: The total number of possible game states is calculated as cars raised to the power of cars (i.e., cars ^ cars). This represents the maximum number of memory slots that might be needed.

_createSnapMapMemorySpace() Function

The contract has a function named _createSnapMapMemorySpace responsible for allocating the memory space based on the calculated size.

https://github.com/JensonCollins/rush-hour-puzzle/blob/main/contracts/RushHourSolver.sol#L359

Optimizing Memory Usage (is3Len parameter)

To potentially reduce memory allocation size, we can introduce an optional parameter is3Len. This flag might indicate if any car on the board has a length of 3 units.

Impact on Weight: Cars with a length of 3 can occupy more than one grid space simultaneously. This can affect the total number of possible game states, potentially reducing the required memory allocation compared to the cars ^ cars formula.

Step Count and Stack Overflow Protection

During the search process, a variable named stepNum might track the depth within the exploration tree (representing the number of moves made).

Stack Overflow Risk: Solidity has limitations on stack usage. If the search goes too deep (i.e., stepNum becomes too large), a StackOverflow error might occur.
Mitigating the Risk: To prevent this error, I declared a constant MAX_STACK_DEEP (e.g., set to 36) to limit the exploration depth.

Efficient Single Byte Storage with Assembly

Solidity v0.8 introduced the mstore8 assembly opcode. This allows setting a single byte in memory storage.

Saving Step Count: We can leverage mstore8 to store the stepNum value in just one byte within the allocated memory space.
mstore8

Conclusion

Memory mapping for Rush Hour in Solidity is an innovative concept with potential benefits. However, careful consideration of memory constraints and trade-offs is crucial before implementing it in real-world applications. For complex scenarios, alternative approaches like efficient data structures and heuristic search algorithms might be more practical.

DEV Community: Jenson