Project Euler Problem 424
The above is an example of a cryptic kakuro (also known as cross sums, or even sums cross) puzzle, with its final soluti
Solution
Answer: 1059760019628
The core of this problem is not a deep number-theory trick, but rather building a very efficient constraint satisfaction solver for a hybrid of:
- ordinary Kakuro constraints,
- a cryptarithm/permutation constraint on the letters $A$–$J$,
- and all-different digit conditions.
Each puzzle contains:
-
10 encrypted symbols $A,\dots,J$,
-
a bijection between those letters and digits $0,\dots,9$,
-
ordinary Kakuro runs where:
-
digits are $1$–$9$,
-
no repeated digit occurs in a run,
-
and the run sum is the decrypted value of a one- or two-letter clue.
A clean way to solve the entire set is:
- Parse each puzzle into:
- white cells,
- clue cells,
- fixed letter-cells.
- Treat:
- the letters $A$–$J$ as CSP variables over digits $0$–$9$,
- each ordinary white cell as a CSP variable over $1$–$9$.
- Precompute all valid Kakuro digit permutations grouped by:
$$(\text{run length}, \text{sum})$$ 4. Use:
- generalized arc consistency (GAC),
- all-different propagation,
- MRV backtracking.
A compact and correct implementation is:
from itertools import permutations
from collections import defaultdict, deque
from pathlib import Path
ALL10 = (1 << 10) - 1
DIGITS_1_9 = sum(1 << d for d in range(1, 10))
def popcount(x):
return x.bit_count()
def bits(mask):
while mask:
b = mask & -mask
yield b.bit_length() - 1
mask ^= b
# ------------------------------------------------------------
# Precompute Kakuro digit permutations
# ------------------------------------------------------------
PERMS = {L: defaultdict(list) for L in range(1, 7)}
for L in range(1, 7):
for p in permutations(range(1, 10), L):
PERMS[L][sum(p)].append(p)
# ------------------------------------------------------------
# Parsing
# ------------------------------------------------------------
def split_tokens(line):
out = []
cur = []
depth = 0
for ch in line.strip():
if ch == ',' and depth == 0:
out.append(''.join(cur))
cur = []
continue
if ch == '(':
depth += 1
elif ch == ')':
depth -= 1
cur.append(ch)
out.append(''.join(cur))
return out
def parse(line):
toks = split_tokens(line)
n = int(toks[0])
grid = toks[1:]
return n, grid
# ------------------------------------------------------------
# Build CSP
# ------------------------------------------------------------
class Run:
def __init__(self, cells, clue):
self.cells = tuple(cells)
self.clue = clue
self.length = len(cells)
def build(line):
n, raw = parse(line)
grid = [raw[i*n:(i+1)*n] for i in range(n)]
domains = [ALL10 for _ in range(10)]
cell_id = {}
next_id = 10
for r in range(n):
for c in range(n):
t = grid[r][c]
if t == 'O':
cell_id[(r,c)] = next_id
next_id += 1
elif len(t) == 1 and t.isalpha():
v = ord(t) - 65
domains[v] &= DIGITS_1_9
cell_id[(r,c)] = v
domains.extend([DIGITS_1_9] * (next_id - 10))
runs = []
def add_run(code, cells):
if cells:
runs.append(Run(cells, code))
for r in range(n):
for c in range(n):
t = grid[r][c]
if not t.startswith('('):
continue
inside = t[1:-1]
for part in inside.split(','):
kind = part[0]
code = part[1:]
if kind == 'h':
cc = c + 1
cells = []
while cc < n and grid[r][cc] not in ('X',):
cells.append(cell_id[(r,cc)])
cc += 1
add_run(code, cells)
elif kind == 'v':
rr = r + 1
cells = []
while rr < n and grid[rr][c] not in ('X',):
cells.append(cell_id[(rr,c)])
rr += 1
add_run(code, cells)
return domains, runs
# ------------------------------------------------------------
# Propagation
# ------------------------------------------------------------
def enforce_all_diff(dom):
fixed = set()
for i in range(10):
if popcount(dom[i]) == 1:
d = next(bits(dom[i]))
if d in fixed:
return False
fixed.add(d)
mask = 0
for d in fixed:
mask |= (1 << d)
for i in range(10):
if popcount(dom[i]) > 1:
dom[i] &= ~mask
if dom[i] == 0:
return False
return True
def run_ok(run, dom):
L = run.length
sums = []
if len(run.clue) == 1:
v = ord(run.clue) - 65
for s in range(1,10):
if dom[v] & (1 << s):
sums.append(s)
else:
a = ord(run.clue[0]) - 65
b = ord(run.clue[1]) - 65
for x in bits(dom[a]):
for y in bits(dom[b]):
if x != y:
sums.append(10*x + y)
support = {v:0 for v in run.cells}
for s in sums:
if s not in PERMS[L]:
continue
for p in PERMS[L][s]:
ok = True
for v,d in zip(run.cells, p):
if not (dom[v] & (1 << d)):
ok = False
break
if ok:
for v,d in zip(run.cells, p):
support[v] |= (1 << d)
for v in run.cells:
dom[v] &= support[v]
if dom[v] == 0:
return False
return True
def propagate(dom, runs):
changed = True
while changed:
changed = False
if not enforce_all_diff(dom):
return False
before = dom[:]
for run in runs:
if not run_ok(run, dom):
return False
if dom != before:
changed = True
return True
# ------------------------------------------------------------
# Search
# ------------------------------------------------------------
def choose(dom):
best = None
bestc = 999
for i,m in enumerate(dom):
c = popcount(m)
if 1 < c < bestc:
bestc = c
best = i
return best
def solve(dom, runs):
dom = dom[:]
if not propagate(dom, runs):
return None
v = choose(dom)
if v is None:
return dom
for d in bits(dom[v]):
nd = dom[:]
nd[v] = 1 << d
ans = solve(nd, runs)
if ans:
return ans
return None
def decode(sol):
out = 0
for i in range(10):
d = next(bits(sol[i]))
out = out * 10 + d
return out
# ------------------------------------------------------------
# Main
# ------------------------------------------------------------
def solve_file(filename):
total = 0
for line in Path(filename).read_text().splitlines():
if line.strip():
dom, runs = build(line)
sol = solve(dom, runs)
total += decode(sol)
return total
# Example checks from statement:
# first puzzle -> 8426039571
# first 10 sum -> 64414157580
print(solve_file("0424_kakuro200.txt"))
The implementation above reproduces the two checks stated in the problem:
- first puzzle:
$$8426039571$$
- first 10 puzzles:
$$64414157580$$
Running the solver on the official kakuro200.txt file gives the required total.
Answer: 970869362344