Problem dossier · Algorithms & Simulation
Minimal superpermutations — extended search
Push the computational frontier on shortest superpermutations: close the 867–872 gap at n = 6 and improve constructions for n = 7–8.
§1
Status
Open search frontier. The problem reduces to a TSP over permutation-overlap graphs — enormous but heavily structured.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Symmetry-reduced branch-and-bound and SAT encodings at n = 6; recombine Egan-style construction fragments; use the search as a benchmark for learned heuristics.
Tags: superpermutations · tsp · search · sat
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Algorithms & Simulation and adjacent territory.
- Heuristics vs. exact methods on NP-hard problems — Algorithms & Simulation
- Map folding & polyomino folding — Algorithms & Simulation
- Self-avoiding walks — Algorithms & Simulation
- Small hard CSP/SAT instances — Algorithms & Simulation
- No-three-in-line problem — Graph Theory
- Superpermutation problem — Combinatorics