{"id":"no-three-in-line","name":"No-three-in-line beyond the solved grids","family":"combinatorics","description":"Dudeney's no-three-in-line problem on the first grids where 2n points are not known to fit: choose as many points of the n x n grid as possible with no three collinear, for n = 75 and 77..80. Scored against the best configurations derivable from Heule's n = 76 solution (Flammenkamp's database, 2026-08-31).","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["solver.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# No-three-in-line beyond the solved grids\n\n## Goal\n\n`solver.py` exposes `solve(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]`: a list\nof distinct grid points `(row, col)` with integer coordinates in `0..n-1` such that no three of them\nlie on a common straight line, in any direction (rows, columns, diagonals and every rational slope).\nMaximise the number of points.\n\nTwo points per row is the obvious ceiling, so `2n` is the most that can ever fit, and Dudeney's\n1906 puzzle asks whether `2n` always fits. It does for every `n <= 74` and for `n = 76`\n(Flammenkamp's no-three-in-line page, database cut 2026-08-31: the `n = 76` configuration is\nMarijn Heule's, found with a new SAT solver on 2026-08-10, quarter-turn symmetric; the odd sizes up\nto 73 are Prellberg's and Heule's from 2025-2026). Guy and Kelly conjectured in 1968 that only\nfinitely many `n` admit `2n` points, and that asymptotically only about `1.814 n` fit. The grids in\nthis pack, `n = 75` and `n = 77..80`, are exactly the first ones where nobody has found `2n`\npoints. A `2n`-point configuration for any of them is a first; anything above the derived records\nbelow is a new lower bound.\n\n## Instances and records\n\nNo sub-`2n` best is published for these `n` (Flammenkamp's database stores full solutions only),\nso the records are what can be derived from Heule's `n = 76` solution, re-verified by this pack's\nown checker on 2026-09-07:\n\n| n | best known | 2n | proven optimal | how the record was obtained |\n|---|---|---|---|---|\n| 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 |\n| 77 | 152 | 154 | no | embed the 76 x 76 solution; no cell can be added at any offset |\n| 78 | 153 | 156 | no | embed at the best offset and add the exact maximum of extra points (1) |\n| 79 | 154 | 158 | no | same, 2 extra points |\n| 80 | 156 | 160 | no | same, 4 extra points |\n\nSource of the base solution: A. Flammenkamp, *The No-Three-in-Line Problem*,\nhttp://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html, configuration 1 for `n = 76` in the\nlookup form (encoding `obgOoUWblJogsLxKkpzMZKjqzIVxy8BDk6DMeh...`, symmetry class rot4). Extra points\nwere found by exhaustive search over the cells not collinear with any pair of the embedded points.\nFlammenkamp's own near-miss counts (`near_miss_count.txt`, restricted to fully symmetric\nconfigurations) stay below these: 140 for `n = 76`, 148 for `n = 80`.\n\n## Metric\n\n    metric = mean over n in {75, 77, 78, 79, 80} of  points(n) / record(n)\n\nThe eval re-derives everything from the point list you return: integer coordinates inside the grid,\nno repeated points, at most `2n` points, and an exact collinearity test on every triple (integer\ncross products, no floating point). Any violation on any `n` is a failed run (`wrong_answer`), and a\nsolver that raises or overruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only\nchanges the `seed` handed to your solver; the instance set is fixed, so your method has to be\nrobust to its starting point. The output also lists `two_n_reached`, the instances where you hit\nthe ceiling.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no SAT solver. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The default is 20 s per instance, so a full eval takes\n  about 100 s plus a few seconds of verification; use the whole budget.\n- Deterministic given `seed`: use `random.Random(seed)`.\n- Coordinates are `0..n-1`.\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES=75,80` (comma-separated `n` values from the table) runs a subset.\n- `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget.\n\nExample: `ZT_EVAL_INSTANCES=75 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py`.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Keep a blocked-cell set: when a point `q` joins, walk the line through `q` and every existing\n  point (direction reduced by the gcd) and mark every grid cell on it. Adding is then O(|S| n) and\n  \"is this cell legal\" is O(1). Removing a point needs a rebuild, so do removals in batches.\n- Every solution found since 1996 has a symmetry: quarter-turn rotation (rot4, the class of all\n  even records from 44 up, including 76), or reflection in both axes composed with a quarter turn\n  (rct4, the class of every odd record from 47 up). Search over orbits of the symmetry group: one\n  choice fixes four points, the candidate set shrinks fourfold, and the collinearity constraints\n  of a symmetric set are far more structured. Prellberg's 2025 constraint-satisfaction runs and\n  Heule's 2026 SAT runs both work inside a single symmetry class.\n- Rows and columns are exact resources: a `2n` configuration has exactly two points in every row\n  and every column, so a good search treats the row and column counts as hard constraints and\n  spends its effort on the slopes.\n- Hall, Jackson, Sudbery and Wild's hyperbola construction (`x y = k mod p`) gives about `1.5 n`\n  points for free; the best random greedy gets roughly the same. The distance to `2n` is where\n  the search has to work, and near-solutions with `2n - 2` or `2n - 4` points are the natural\n  intermediate targets. The crop of the 76 solution shows why: a 75 x 75 grid with 148 points has\n  no free cell at all, so the last two points need a large rearrangement, not a local move.\n- Since the exact records here come from embedding a larger solution, a solver that finds a\n  `2n`-point set for `n = 77` also gives every smaller grid a near-record by cropping.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for no-three-in-line. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to solve()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per grid size n (default 20)\n  ZT_EVAL_INSTANCES              comma-separated grid sizes n (default \"75,77,78,79,80\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport itertools\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"20\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"75,77,78,79,80\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known number of points of the n x n grid with no three collinear. 2n is the proven maximum\n# (two per row). Flammenkamp's no-three-in-line page (database cut 2026-08-31) has 2n-point\n# configurations for every n <= 74 and for n = 76 (Heule, 2026-08-10, rot4 symmetry), so those n\n# are closed. For n = 75 and n >= 77 no 2n configuration is known and no sub-2n best is published,\n# so the records here are derived from Heule's n = 76 configuration (re-verified with this eval's\n# check): n = 75 is a contiguous 75 x 75 crop of it (148 points, no cell can be added); n = 77..80\n# embed it at every offset and add the exact maximum of further points (0, 1, 2 and 4).\n# Update when a hub-verified submission exceeds these; reaching 2n would be a first for that n.\nRECORDS = {75: 148, 77: 152, 78: 153, 79: 154, 80: 156}\nPROVEN: set[int] = set()\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in solver.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef _coord(v, n: int) -> int:\n    if isinstance(v, bool) or not isinstance(v, (int, float)) or v != int(v):\n        fail(f\"solve({n}) returned a non-integer coordinate {v!r}\", \"wrong_answer\")\n    return int(v)\n\n\ndef validate(points, n: int) -> int:\n    \"\"\"Check the returned point set and return its size. Nothing the solver reports is trusted.\"\"\"\n    if not isinstance(points, (list, tuple, set, frozenset)):\n        fail(f\"solve({n}) must return a list of (row, col) integer pairs\", \"wrong_answer\")\n    pts = []\n    for p in points:\n        try:\n            r, c = p\n        except Exception:\n            fail(f\"solve({n}) returned a non-point {p!r}\", \"wrong_answer\")\n        r, c = _coord(r, n), _coord(c, n)\n        if not (0 <= r < n and 0 <= c < n):\n            fail(f\"solve({n}) placed a point outside the grid: ({r}, {c})\", \"wrong_answer\")\n        pts.append((r, c))\n    if len(set(pts)) != len(pts):\n        fail(f\"solve({n}) returned a repeated point\", \"wrong_answer\")\n    if len(pts) > 2 * n:\n        fail(f\"solve({n}) returned {len(pts)} points; more than 2n forces three in a row\", \"wrong_answer\")\n    # Every triple, exactly: three points are collinear iff the cross product of two edge vectors is 0.\n    for (ar, ac), (br, bc), (cr, cc) in itertools.combinations(pts, 3):\n        if (br - ar) * (cc - ac) - (bc - ac) * (cr - ar) == 0:\n            fail(f\"solve({n}): {(ar, ac)}, {(br, bc)}, {(cr, cc)} are collinear\", \"wrong_answer\")\n    return len(pts)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"solver.py\")\n    sys.dont_write_bytecode = True  # a stale solver.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import solver as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import solver.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"solve\"):\n        fail(\"solver.py must define solve(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"no3inline|{SEED}\").getrandbits(32)\n    per_n, beaten, full = {}, [], []\n    for n in INSTANCES:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            points = cand.solve(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"solve({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"solve({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        size = validate(points, n)\n        per_n[n] = {\"points\": size, \"record\": RECORDS[n], \"bound\": 2 * n, \"proven_optimal\": n in PROVEN,\n                    \"ratio\": round(size / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if size > RECORDS[n]:\n            beaten.append(n)\n        if size == 2 * n:\n            full.append(n)\n    metric = sum(v[\"ratio\"] for v in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_n\": per_n, \"records_beaten\": beaten, \"two_n_reached\": full}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"solver.py":"\"\"\"Baseline: random greedy fill with a blocked-cell set, plus a fixed number of ruin-and-recreate\nrounds. Reaches roughly 1.5n points, well short of the records. Beat it.\"\"\"\n\nimport math\nimport random\nimport time\n\n\ndef solve(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + time_budget\n    cells = [(r, c) for r in range(n) for c in range(n)]\n\n    def block(bl, p, q):\n        \"\"\"Mark every grid cell on the line through p and q (other than p) as unusable.\"\"\"\n        dr, dc = q[0] - p[0], q[1] - p[1]\n        g = math.gcd(abs(dr), abs(dc))\n        dr //= g\n        dc //= g\n        for s in (1, -1):\n            r, c = p[0] + s * dr, p[1] + s * dc\n            while 0 <= r < n and 0 <= c < n:\n                bl.add((r, c))\n                r += s * dr\n                c += s * dc\n\n    def build(keep):\n        pts = list(keep)\n        bl = set(pts)\n        for i in range(len(pts)):\n            for j in range(i):\n                block(bl, pts[j], pts[i])\n        order = cells[:]\n        rng.shuffle(order)\n        for q in order:\n            if q in bl:\n                continue\n            for p in pts:\n                block(bl, p, q)\n            bl.add(q)\n            pts.append(q)\n        return pts\n\n    best = build([])\n    for _ in range(400):  # a fixed round count keeps the result deterministic under seed\n        if time.perf_counter() > deadline:  # only bites when the budget is cut short\n            break\n        cand = build(rng.sample(best, int(len(best) * 0.7)))\n        if len(cand) >= len(best):\n            best = cand\n    return best\n"}}