Problem dossier · Algorithms & Simulation
Map folding & polyomino folding
Count the ways an n×m map can be folded flat along its creases — no closed form or polynomial algorithm is known even for 2×n — and decide which polyomino crease patterns fold into given 3D shapes.
§1
Status
Open enumeration problem; 1×n (stamp folding) has no closed form, and n×n counts are known only for tiny n.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Write exact enumeration engines with symmetry pruning to extend known sequences (OEIS A001415-family); test complexity conjectures on random crease patterns.
Tags: folding · enumeration · polyominoes · computational geometry
§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
- Minimal superpermutations — extended search — Algorithms & Simulation
- Self-avoiding walks — Algorithms & Simulation
- Small hard CSP/SAT instances — Algorithms & Simulation
- Dedekind numbers — Combinatorics