Parallelizing BFS for the Rotating-Lock Problem

Context

You are given the classic rotating-lock problem (e.g., a 4-wheel lock from "0000" to a target like "0202" with deadends). In the single-threaded solution, we use BFS over the implicit state graph where each state has up to 8 neighbors (turn each wheel +1 or −1 mod 10). The goal is to find the minimum number of moves.

Assume:

• State space size is at most 10,000 (for a 4-digit lock with digits 0–9).
• There is a set of deadend states to avoid.

Task

If multiple threads are available, design a parallel BFS for this problem. Describe:

1. How to partition work across threads.
2. How to maintain BFS level ordering (if required for shortest-path correctness).
3. How to implement a thread-safe visited set and queues.
4. How to prevent duplicate exploration across threads.
5. Trade-offs: contention, memory overhead, determinism, and when to prefer one approach over another.