Crate arc_acreage
source ·Expand description
This crate contains two implementations of a backtracking search algorithm to enumerate closed curves in a 7x7 grid, as per the Jane Stree Puzzle ‘Arc Acreage’ from April 2023 (https://www.janestreet.com/puzzles/archive/).
The first implementation was slow but produced the correct answer (depending on the strength of search constraints used, the result took on the order of one hour to return). A faster technique dramatically reduces the search space and does not require proving that any special constraints must hold for curves of our target area. This algorithm returns the result in <100ms.
As required in the original puzzle, there are 89,519,144 closed curves of area 32.
Modules
- A faster implementation of the backtracking search algorithm to generate curves of a desired area.
- The original implementation of a backtracking search algorithm to generate closed curves of a desired area.