File size: 6,709 Bytes
ae02605 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 | """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:
# dead end: restart rather than backtrack; restarts are rare and a
# fresh fill is cheaper than unwinding a deep search
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:]
# a test solution must not appear in training, even up to digit relabelling
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"
# every puzzle must still admit exactly one solution
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)
|