No-three-in-line beyond the solved grids

# No-three-in-line beyond the solved grids ## Goal `solver.py` exposes `solve(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]`: a list of distinct grid points `(row, col)` with integer coordinates in `0..n-1` such that no three of them lie on a common straight line, in any direction (rows, columns, diagonals and every rational slope). Maximise the number of points. Two points per row is the obvious ceiling, so `2n` is the most that can ever fit, and Dudeney's 1906 puzzle asks whether `2n` always fits. It does for every `n <= 74` and for `n = 76` (Flammenkamp's no-three-in-line page, database cut 2026-08-31: the `n = 76` configuration is Marijn Heule's, found with a new SAT solver on 2026-08-10, quarter-turn symmetric; the odd sizes up to 73 are Prellberg's and Heule's from 2025-2026). Guy and Kelly conjectured in 1968 that only finitely many `n` admit `2n` points, and that asymptotically only about `1.814 n` fit. The grids in this pack, `n = 75` and `n = 77..80`, are exactly the first ones where nobody has found `2n` points. A `2n`-point configuration for any of them is a first; anything above the derived records below is a new lower bound. ## Instances and records No sub-`2n` best is published for these `n` (Flammenkamp's database stores full solutions only), so the records are what can be derived from Heule's `n = 76` solution, re-verified by this pack's own checker on 2026-09-07: | n | best known | 2n | proven optimal | how the record was obtained | |---|---|---|---|---| | 75 | 148 | 150 | no | contiguous 75 x 75 crop of the 76 x 76 solution (loses one point per corner row and column); no further cell can be added | | 77 | 152 | 154 | no | embed the 76 x 76 solution; no cell can be added at any offset | | 78 | 153 | 156 | no | embed at the best offset and add the exact maximum of extra points (1) | | 79 | 154 | 158 | no | same, 2 extra points | | 80 | 156 | 160 | no | same, 4 extra points | Source of the base solution: A. Flammenkamp, *The No-Three-in-Line Problem*, http://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html, configuration 1 for `n = 76` in the lookup form (encoding `obgOoUWblJogsLxKkpzMZKjqzIVxy8BDk6DMeh...`, symmetry class rot4). Extra points were found by exhaustive search over the cells not collinear with any pair of the embedded points. Flammenkamp's own near-miss counts (`near_miss_count.txt`, restricted to fully symmetric configurations) stay below these: 140 for `n = 76`, 148 for `n = 80`. ## Metric metric = mean over n in {75, 77, 78, 79, 80} of points(n) / record(n) The eval re-derives everything from the point list you return: integer coordinates inside the grid, no repeated points, at most `2n` points, and an exact collinearity test on every triple (integer cross products, no floating point). Any violation on any `n` is a failed run (`wrong_answer`), and a solver that raises or overruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed, so your method has to be robust to its starting point. The output also lists `two_n_reached`, the instances where you hit the ceiling. ## Constraints - Standard library only. No numpy, no scipy, no SAT solver. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 20 s per instance, so a full eval takes about 100 s plus a few seconds of verification; use the whole budget. - Deterministic given `seed`: use `random.Random(seed)`. - Coordinates are `0..n-1`. ## Iterating quickly - `ZT_EVAL_INSTANCES=75,80` (comma-separated `n` values from the table) runs a subset. - `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget. Example: `ZT_EVAL_INSTANCES=75 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py`. ## Ideas that are known to matter (check the journal before repeating one) - Keep a blocked-cell set: when a point `q` joins, walk the line through `q` and every existing point (direction reduced by the gcd) and mark every grid cell on it. Adding is then O(|S| n) and "is this cell legal" is O(1). Removing a point needs a rebuild, so do removals in batches. - Every solution found since 1996 has a symmetry: quarter-turn rotation (rot4, the class of all even records from 44 up, including 76), or reflection in both axes composed with a quarter turn (rct4, the class of every odd record from 47 up). Search over orbits of the symmetry group: one choice fixes four points, the candidate set shrinks fourfold, and the collinearity constraints of a symmetric set are far more structured. Prellberg's 2025 constraint-satisfaction runs and Heule's 2026 SAT runs both work inside a single symmetry class. - Rows and columns are exact resources: a `2n` configuration has exactly two points in every row and every column, so a good search treats the row and column counts as hard constraints and spends its effort on the slopes. - Hall, Jackson, Sudbery and Wild's hyperbola construction (`x y = k mod p`) gives about `1.5 n` points for free; the best random greedy gets roughly the same. The distance to `2n` is where the search has to work, and near-solutions with `2n - 2` or `2n - 4` points are the natural intermediate targets. The crop of the 76 solution shows why: a 75 x 75 grid with 148 points has no free cell at all, so the last two points need a large rearrangement, not a local move. - Since the exact records here come from embedding a larger solution, a solver that finds a `2n`-point set for `n = 77` also gives every smaller grid a near-record by cropping. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.