Abstract
Determining the diameter of massive combinatorial state spaces is a fundamental challenge in computational search. Standard Breadth-First Search (BFS) is often limited by memory constraints, as it requires storing every visited state to avoid redundant computations. This paper introduces Two-Bit Breadth-First Search (TBBFS), a highly memory-efficient algorithm that utilizes only two bits per state. By leveraging "operator locality" and optimized disk I/O strategies, TBBFS enables exhaustive searches of spaces containing trillions of states. The algorithm was successfully applied to determine the diameters of the 15-pancake and 12-burned-pancake problems for the first time, outperforming previous state-of-the-art implementations by a factor of five.
Introduction
In the study of combinatorial puzzles like the Rubik’s Cube or the Pancake Problem, a key objective is finding the "diameter"—the maximum number of moves required to solve any configuration from the goal state. While BFS is the standard approach for finding shortest paths, the "state-space explosion" often makes it impractical. For many puzzles, the number of possible configurations reaches into the trillions, far exceeding the RAM capacity of modern workstations.
Previous attempts to mitigate this, such as Frontier Search, reduce memory usage by only storing the current search boundary. However, these methods fail when the "width" of the search (the number of states at a given depth) is a significant fraction of the total state space. TBBFS addresses this by providing a robust mechanism for external-memory search, allowing the "visited" list to reside primarily on disk.
The Two-Bit Breadth-First Search (TBBFS) Algorithm
The core of TBBFS is a compact state representation. Each state in the search space is mapped to a unique integer index in a large array, where each entry consists of only two bits. These bits represent four possible statuses: Old (reached in a previous depth), Current (at the current depth being expanded), Next (a child of a current state), and New (not yet reached).
Technical Innovations
To handle state spaces that exceed RAM, TBBFS employs several critical optimizations:
- Bijective Mapping and Disk Segmentation: The state space is divided into segments stored on magnetic disks. Only one segment is loaded into memory at a time for processing.
- Operator Locality: This is the algorithm's most significant optimization. By designing the mapping function such that a move (operator) typically results in a child state with a numerically similar index to its parent, the algorithm ensures that many updates occur within the same memory-resident segment. This drastically reduces the frequency of slow disk writes.
- Delayed Updates: When a child state belongs to a segment currently on disk, the update is logged to a temporary file. These logs are processed sequentially when the corresponding segment is eventually loaded into RAM.
Experimental Results
The TBBFS algorithm was evaluated on several classic combinatorial problems, including the Pancake Problem and its "burned" variant. In the Pancake Problem, the goal is to sort a stack of pancakes of different sizes using only prefix flips. The "burned" version adds the constraint that each pancake has a specific orientation.
As shown in Table 1, TBBFS established new records for these problems. Specifically, it was determined that the diameter for 15 pancakes is 17 flips, and for 12 burned pancakes, it is 21 flips. The search for 15 pancakes involved 1.3 trillion states and took approximately 41 days to complete, managing a 327 GB array on disk.
The scale of these searches is further illustrated in Table 2, which shows the distribution of states across different depths for a massive search space (approximately 981 billion states). The "fat" nature of these distributions—where the number of states at intermediate depths is enormous—highlights why TBBFS is superior to Frontier Search for these specific problems.
Conclusion
TBBFS represents a significant advancement in external-memory search algorithms. By combining a minimal 2-bit state representation with disk-aware optimizations like operator locality, it allows researchers to explore state spaces that were previously considered unreachable. The discovery of new diameters for the pancake problems and the identification of anomalies in the 11-burned pancake problem demonstrate the algorithm's power. Future work will likely focus on leveraging faster storage technologies, such as NVMe SSDs, to further reduce the I/O bottleneck.
Summary updated