| """Generate a HARD Sudoku benchmark, with every puzzle verified unique. |
| |
| The SATNet split is saturated - search-free constraint propagation solves |
| 1000/1000 of it - so nothing measured there discriminates between methods. This |
| builds instances that do. |
| |
| Each puzzle is MINIMAL: cells are removed from a completed grid in random order |
| and a removal is kept only if the solution is still unique, verified by an |
| exhaustive counter that stops at two. The result carries roughly 19-30 clues |
| (mean 24), where constraint propagation alone solves about 4%. No puzzle is accepted without |
| that uniqueness check, so board accuracy remains a well-defined quantity. |
| |
| Solutions come from a randomised backtracking fill of an EMPTY grid, which |
| reaches the full space of roughly 6.7e21 valid grids. |
| |
| An earlier version applied the Sudoku symmetry group to a single seed grid |
| instead. That was much faster and completely wrong: every grid it produced lay |
| in one equivalence class, whose size modulo digit relabelling is only about 3.4 |
| million, so 101,000 draws collided constantly and 767 of 1000 test solutions |
| already appeared in training. The assertion below caught it. It is kept, and it |
| is the reason the slower fill is used. |
| |
| Train and test are built from DISJOINT solution grids and the script asserts |
| that no test solution appears in training, in any relabelling. |
| """ |
| import argparse, os, sys, time |
| from multiprocessing import Pool |
|
|
| import numpy as np |
|
|
| sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) |
| from sudoku import CELLS, GRID |
|
|
| PEERS = None |
|
|
|
|
| def _peers(): |
| out = [] |
| for i in range(CELLS): |
| r, c = divmod(i, GRID) |
| br, bc = 3 * (r // 3), 3 * (c // 3) |
| s = set() |
| for k in range(GRID): |
| s.add(r * GRID + k) |
| s.add(k * GRID + c) |
| for dr in range(3): |
| for dc in range(3): |
| s.add((br + dr) * GRID + bc + dc) |
| s.discard(i) |
| out.append(sorted(s)) |
| return out |
|
|
|
|
| PEERS = _peers() |
|
|
|
|
|
|
| def candidates(g): |
| cand = [0x1FF if v == 0 else (1 << (v - 1)) for v in g] |
| for i, v in enumerate(g): |
| if v: |
| bit = 1 << (v - 1) |
| for p in PEERS[i]: |
| if cand[p] & bit: |
| cand[p] &= ~bit |
| if cand[p] == 0: |
| return None |
| return cand |
|
|
|
|
| def count_solutions(grid, limit=2): |
| g = [int(v) for v in grid] |
|
|
| def rec(): |
| cand = candidates(g) |
| if cand is None: |
| return 0 |
| best, bi = 10, -1 |
| for i in range(CELLS): |
| if g[i] == 0: |
| n = bin(cand[i]).count("1") |
| if n < best: |
| best, bi = n, i |
| if n == 1: |
| break |
| if bi < 0: |
| return 1 |
| tot = 0 |
| for d in range(9): |
| if cand[bi] & (1 << d): |
| g[bi] = d + 1 |
| tot += rec() |
| g[bi] = 0 |
| if tot >= limit: |
| return tot |
| return tot |
|
|
| return rec() |
|
|
|
|
| def random_solution(rng): |
| """A uniformly-ish random completed grid, by randomised backtracking fill. |
| |
| The previous version applied the Sudoku symmetry group to a single seed grid. |
| Every grid it produced therefore lay in ONE equivalence class, whose size |
| modulo digit relabelling is only about 3.4 million - so drawing 101,000 |
| samples collided constantly, and 767 of 1000 test solutions turned out to |
| already appear in training. Filling an empty grid instead reaches the full |
| space of roughly 6.7e21 valid grids, where collisions are impossible in |
| practice. |
| """ |
| g = [0] * CELLS |
| while True: |
| cand = candidates(g) |
| if cand is None: |
| return None |
| best, bi = 10, -1 |
| for i in range(CELLS): |
| if g[i] == 0: |
| n = bin(cand[i]).count("1") |
| if n < best: |
| best, bi = n, i |
| if bi < 0: |
| return np.array(g, dtype=np.int64) |
| digits = [d + 1 for d in range(9) if cand[bi] & (1 << d)] |
| rng.shuffle(digits) |
| placed = False |
| for d in digits: |
| g[bi] = d |
| if candidates(g) is not None: |
| placed = True |
| break |
| g[bi] = 0 |
| if not placed: |
| |
| |
| g = [0] * CELLS |
|
|
|
|
| def make_one(seed): |
| rng = np.random.default_rng(seed) |
| sol = None |
| while sol is None: |
| sol = random_solution(rng) |
| g = [int(v) for v in sol] |
| for c in rng.permutation(CELLS): |
| keep = g[c] |
| g[c] = 0 |
| if count_solutions(g, 2) != 1: |
| g[c] = keep |
| return np.array(g, dtype=np.int64), sol |
|
|
|
|
| def canon(g): |
| m, out = {}, [] |
| for v in g: |
| if v not in m: |
| m[v] = len(m) + 1 |
| out.append(m[v]) |
| return bytes(out) |
|
|
|
|
| if __name__ == "__main__": |
| p = argparse.ArgumentParser() |
| p.add_argument("--n_train", type=int, default=100000) |
| p.add_argument("--n_test", type=int, default=1000) |
| p.add_argument("--workers", type=int, default=64) |
| p.add_argument("--out", default="data/sudoku_hard") |
| a = p.parse_args() |
| os.makedirs(a.out, exist_ok=True) |
|
|
| total = a.n_train + a.n_test |
| t0 = time.time() |
| with Pool(a.workers) as pool: |
| got = pool.map(make_one, range(total), chunksize=32) |
| P = np.stack([g for g, _ in got]) |
| S = np.stack([s for _, s in got]) |
| print(f"generated {len(P)} minimal puzzles in {time.time()-t0:.0f}s", flush=True) |
| print(f"clues: min={(P>0).sum(1).min()} max={(P>0).sum(1).max()} " |
| f"mean={(P>0).sum(1).mean():.1f}", flush=True) |
|
|
| Ptr, Str = P[:a.n_train], S[:a.n_train] |
| Pte, Ste = P[a.n_train:], S[a.n_train:] |
|
|
| |
| tr = {canon(r) for r in Str} |
| leak = sum(canon(r) in tr for r in Ste) |
| print(f"test solutions also in training (up to relabelling): {leak}", flush=True) |
| assert leak == 0, "leakage between train and test" |
|
|
| |
| bad = sum(count_solutions(Pte[i], 2) != 1 for i in range(0, len(Pte), 25)) |
| print(f"test puzzles without a unique solution (sampled): {bad}", flush=True) |
| assert bad == 0 |
|
|
| np.save(os.path.join(a.out, "train_puz.npy"), Ptr) |
| np.save(os.path.join(a.out, "train_sol.npy"), Str) |
| np.save(os.path.join(a.out, "test_puz.npy"), Pte) |
| np.save(os.path.join(a.out, "test_sol.npy"), Ste) |
| print(f"saved to {a.out}: train {Ptr.shape} test {Pte.shape}", flush=True) |
|
|
