Richard E. Korf
We present a breadth-first search algorithm, two-bit breadth-first search (TBBFS), which requires only two bits for each state in the problem space. TBBFS can be parallelized in several ways, and can store its data on magnetic disk. Using TBBFS, we perform complete breadth-first searches of the original pancake problem with 14 and 15 pancakes, and the burned pancake problem with 11 and 12 pancakes, determining the diameter of these problem spaces for the first time. We also perform the first complete breadth-first search of the subspace of Rubik's Cube determined by the edge cubies.
Subjects: 15.7 Search; 15. Problem Solving
Submitted: Apr 15, 2008