A pattern database (PDB) is a lookup table that stores exact shortest distances for a reduced version of a problem. During search, the current state is projected to the reduced representation and the stored distance is used as an admissible heuristic (a lower bound) for the full problem.
- Select a pattern (e.g. subset of cubies / features).
- Define an abstraction (reduced state space) that keeps only the pattern-relevant information.
- Run BFS from the goal in the reduced space (retrograde construction).
- Store the exact distance-to-goal for every abstract state.
- Project the full state to the abstract pattern state.
- Compute a unique index for the abstract state.
- Lookup
h(n) from the table.
- Use
h(n) inside A* or IDA* in case of limited memory.
Let:
- S be the full state space,
- S′ be the abstract state space,
- π:S→S′ be the projection (abstraction mapping),
- d′(s′) be the exact goal distance in the abstract space.
Because abstraction removes constraints/details, solving the abstract problem cannot be harder than solving the original problem. Therefore the abstract distance is a lower bound on the real distance:
h(s):=d′(π(s))≤d(s),
so h is admissible.
Korf constructs three PDBs and combines them safely via a maximum.
- Entries:
8!⋅37=88,179,840
- Stored distances: 0,…,11 (fits in 4 bits)
- Storage: ≈42MB with 4-bit packing
For each chosen set of 6 edges:
- Entries:
6!12!⋅26=42,577,920
- Stored distances: 0,…,10 (fits in 4 bits)
- Storage: ≈20MB per table
Total storage for all three tables is ≈82MB.
For Rubik’s Cube, a single move can affect multiple cubies simultaneously, so corner and edge abstractions are not additive in a way that guarantees correctness. Korf therefore uses:
h(s)=max(hcorners(s),hedgesA(s),hedgesB(s)).
This preserves admissibility while strengthening pruning.
Summing heuristics is admissible only when abstractions are constructed so that move costs can be safely distributed (additive / disjoint abstractions). This is not the combination strategy used in Korf (1997) for the cube.
Distances are small, so storing each entry in a nibble gives:
- 2 entries per byte
- reduced memory footprint with cache-friendly sequential arrays
The lookup path is on the hot loop of node expansion:
- encode orientations compactly
- rank permutations with combinatorial indexing
- avoid allocations and hashing
PDB construction is expensive once and then reused across many solves with the same goal state.
- Richard E. Korf. Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. AAAI (1997).