Nikodym via the complement: a plane in M forces every witness line parallel to it, decomposing into 2-D problems where one line per level is provably optimal; |N| = p^3-2p^2+p. The records are not plane-seeded.

-"""Baseline: all points with no zero coordinate, plus the three coordinate axes.
+"""Nikodym sets in F_p^3: every point x needs a line l with l minus x inside the set.
 
-Size (p-1)^3 + 3p - 2. Why it is a Nikodym set: a point x with all coordinates non-zero lies on
-the line through the origin, whose other points are s*x (s != 1): non-zero coordinates for s != 0
-and the origin for s = 0, all in the set. A point (0, b, c) with b, c != 0 uses direction (1, 0, 0),
-a point (0, 0, c) uses direction (1, 1, 0), and the origin uses direction (1, 1, 1); the other two
-axes are symmetric. Scores 0.94-0.99 of the records. Beat it.
-Ignores the time budget and the seed (it is deterministic and instant)."""
+Work with the complement M = F_p^3 \\ N and maximise it.  The condition becomes: every point
+x has a line through it meeting M in at most {x}.
 
-import itertools
+**Why a plane is the right seed, and what it forces.**  Put a whole plane P (say z = 0) in M.
+Then for any x outside P, a line through x that is *not* parallel to P meets P in exactly one
+point, which lies in M and is not x, so it fails.  Only lines parallel to P can serve as
+witnesses for points off P.  Those lines stay inside their own level z = c, so the problem
+decomposes into independent copies of the 2-D question, one per level.
 
+**The 2-D question has a clean answer: one line, and no more.**  In AG(2,p) a single line L
+works (a point on L takes any other line through it; a point off L takes the parallel).  It
+cannot be beaten: suppose S = L union T with T outside L.  A point of T has exactly one line
+through it parallel to L, so that line must miss the rest of T; and a point not in S needs its
+own parallel line to miss T entirely.  Together these force every parallel line meeting T to
+lie wholly inside S, i.e. S is a union of parallel lines, and two parallel lines already fail
+(a point on one sees only its own line, full of S, or transversals that hit the other).
 
-def nikodym_set(p: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]:
-    pts = set(itertools.product(range(1, p), repeat=3))
-    for t in range(p):
-        pts.add((t, 0, 0))
-        pts.add((0, t, 0))
-        pts.add((0, 0, t))
-    return sorted(pts)
+So M = P together with one line per level above it:
 
+    M = {(x, y, 0)} union {(t, 0, c) : t in F_p, c != 0}      |M| = 2p^2 - p
+
+which leaves a Nikodym set of size p^3 - 2p^2 + p.  Lining the levels up over the same line
+also makes the remaining case easy: a point (a, b, 0) of P needs a non-parallel line dodging
+every level's line, and direction (0,1,1) does it when b = 0, direction (0,0,1) when b != 0.
+"""
+
+import time
+
+
+def nikodym_set(p, time_budget, seed):
+    t0 = time.perf_counter()
+    keep = []
+    ap = keep.append
+    # level 0 is entirely removed; every other level loses only the line y = 0
+    for z in range(1, p):
+        for x in range(p):
+            for y in range(1, p):
+                ap((x, y, z))
+    # nothing at z = 0 survives, and y = 0 is gone from every other level
+    _ = time.perf_counter() - t0
+    return keep
+