You write the obvious Kakuro solver first: try 1 through 9 in each empty cell, and back up whenever a sum goes wrong. The series 7x7 grid has 24 white cells. Trying every digit in every cell is 9²⁴ combinations, about 8 × 10²², and your laptop’s fan has opinions about that.
The fix isn’t a faster computer. It’s using what Kakuro already tells you. A clue of 6 over three cells doesn’t allow 729 possibilities. It allows exactly one set of digits, {1, 2, 3}, in some order. Build the solver around the sets each clue allows and the search shrinks to almost nothing.
A generator needs more than a solver, though. It has to prove there’s no second solution and say how hard the puzzle is. This article builds all three on one core, in plain Python with no dependencies, and tests them on the three versions of the series grid: Main (one solution, Medium), Draft (two solutions) and Hard (one solution, needs a region count).
Kakuro as a Search Problem
NP-Completeness in Plain Terms
Solving Kakuro in general is NP-complete. In practice, that means nobody knows a method that stays fast as grids grow without limit. Takahiro Seta showed it in a 2002 thesis, and Oliver Ruepp and Markus Holzer published a new proof in 2010.
It doesn’t mean your solver will be slow. Published grids are small, and every clue cuts the possibilities sharply. With the pruning below, the series grids solve in a few milliseconds. NP-completeness is a statement about the worst case on enormous grids, not about a 7x7 on your desk.
Cells, Candidates and Constraints
Frame the puzzle the way a constraint solver would:
- Variables: each white cell.
- Candidates: the digits each cell might still hold, starting at 1–9.
- Constraints: each run’s digits add up to its clue, and no digit repeats within a run. Every cell belongs to one across run and one down run and has to satisfy both.
Everything below works by shrinking candidates until each cell has one left.
The Core Pieces
The code is one file, kakuro.py, shown in eight pieces. Paste them in order and you have the whole script. It needs Python 3.10 or later for int.bit_count() and nothing outside the standard library.
Combination Tables as Bitmasks
Store a set of digits as a 9-bit integer: bit 0 is digit 1, bit 8 is digit 9. The set {1, 2} is 0b000000011, and {1, 2, 3} is 0b000000111. Checking which digits two sets share is a single &.
Then precompute every digit set for every run length and total, using itertools.combinations. There are only 511 non-empty subsets of 1–9, so the whole table is tiny.
r"""kakuro.py: solve, count, grade and generate Kakuro puzzles.
Python 3.10+ (uses int.bit_count), standard library only.
Grid format: one line per row, cells separated by spaces.
# black cell with no clue
. white cell
16\ clue cell: down 16
\12 clue cell: across 12
19\8 clue cell: down 19 and across 8
"""
import itertools
import random
import sys
FULL = 0b111111111 # candidates 1-9: bit k means digit k + 1
def bits(mask):
"""Yield each set bit of mask as its own one-bit mask."""
while mask:
low = mask & -mask
yield low
mask ^= low
def digit(bit):
"""Convert a one-bit mask back to its digit (0b100 -> 3)."""
return bit.bit_length()
# COMBOS[(length, total)] -> every digit set (as a mask) that fills the run.
COMBOS = {}
for length in range(1, 10):
for combo in itertools.combinations(range(1, 10), length):
mask = sum(1 << (d - 1) for d in combo)
COMBOS.setdefault((length, sum(combo)), []).append(mask)
COMBOS[(2, 3)] is [0b11], the single set {1, 2}. COMBOS[(4, 27)] holds three masks: {3, 7, 8, 9}, {4, 6, 8, 9} and {5, 6, 7, 9}.
Reading the Grid
Grids are plain text, one line per row, using the same down\across notation as the rest of this series. 16\ is a down clue of 16, \12 is an across clue of 12, 19\8 is both, # is an empty black cell and . is a white cell. Here’s the series Main grid as main.txt:
# 16\ 12\ 10\ 8\ # #
\12 . . . . # #
\27 . . . . 21\ #
\3 . . 19\8 . . 6\
# \8 . . 17\8 . .
# # \16 . . . .
# # \27 . . . .
The parser walks every non-white cell and collects the white cells to its right and below. Each group becomes a run.
# ---------------------------------------------------------------- parsing
def read_grid(text):
"""Return (cells, runs). Each run is (cells, total, name); total may be None."""
rows = [line.split() for line in text.strip().splitlines()]
runs = []
for r, row in enumerate(rows):
for c, tok in enumerate(row):
if tok == ".":
continue
down, across = tok.split("\\") if "\\" in tok else ("", "")
# An across run starts right of any black cell followed by white cells.
cells = []
cc = c + 1
while cc < len(row) and row[cc] == ".":
cells.append((r, cc))
cc += 1
if cells:
runs.append((cells, int(across) if across else None, f"across r{r}c{c + 1}"))
# A down run starts below any black cell followed by white cells.
cells = []
rr = r + 1
while rr < len(rows) and rows[rr][c] == ".":
cells.append((rr, c))
rr += 1
if cells:
runs.append((cells, int(down) if down else None, f"down r{r + 1}c{c}"))
whites = sorted({x for run_cells, _, _ in runs for x in run_cells})
return whites, runs
A run whose total is None has no clue. That’s fine for a blank layout, which the generator uses later. For a puzzle, it means the grid is malformed, and the solver will report no solution.
Run-Level Filtering (the Step That Matters Most)
This is where Kakuro differs from a generic constraint solver. For each run:
- Keep only the digit sets that still fit. A set fits if its digits can go one per cell, with each digit inside that cell’s current candidates.
- Narrow each cell to the digits that appear in some surviving set, and that leave a valid placement for the rest of the run.
Repeat for every run until nothing changes. Because every cell sits in an across run and a down run, narrowing one run narrows its crossings on the next pass.
# ------------------------------------------------------- run-level filter
def fits(cells, mask, cand):
"""Can the digits in mask go one per cell, each within that cell's candidates?"""
if not cells:
return mask == 0
first, rest = cells[0], cells[1:]
for bit in bits(cand[first] & mask):
if fits(rest, mask ^ bit, cand):
return True
return False
def propagate(cand, runs):
"""Narrow every cell to digits that appear in a still-possible set for its runs.
Repeats until nothing changes. Returns False if some cell runs out of digits.
"""
changed = True
while changed:
changed = False
for cells, total, _ in runs:
live = [m for m in COMBOS.get((len(cells), total), []) if fits(cells, m, cand)]
for x in cells:
others = [y for y in cells if y != x]
allowed = 0
for m in live:
for bit in bits(cand[x] & m & ~allowed):
if fits(others, m ^ bit, cand):
allowed |= bit
if allowed != cand[x]:
if allowed == 0:
return False
cand[x] = allowed
changed = True
return True
def is_solved(cand):
return all(m.bit_count() == 1 for m in cand.values())
On the Main grid, the first thing this finds is r6c6 = 3. The 6 down along the right edge can only be {1, 2, 3}, the 27 across along the bottom can’t include 1 or 2, and 3 is the only digit left in their shared cell. Keep filtering and every cell on the Main grid resolves without a single guess. On the Hard grid it places 7 cells and stalls.
Plain forward checking, which only removes a placed digit from its neighbors, is much weaker. It doesn’t know that a 6 over three cells means {1, 2, 3}, so it can’t find r6c6 until it has guessed its way close. Run-level filtering does most of the solver’s work.
Backtracking with Fewest-Candidates-First
When filtering stalls, pick the open cell with the fewest candidates, try each one, filter again and recurse. Picking cells in reading order instead wastes time on cells that could still be almost anything. Copying the candidate dictionary before each trial makes undoing a failed branch free.
# ------------------------------------------------------------- searching
def solve(cand, runs, limit=2, found=None):
"""Collect up to `limit` solutions. Filter first, then branch on the tightest cell."""
found = [] if found is None else found
cand = dict(cand)
if not propagate(cand, runs):
return found
open_cells = [x for x in cand if cand[x].bit_count() > 1]
if not open_cells:
found.append({x: digit(m) for x, m in cand.items()})
return found
x = min(open_cells, key=lambda y: cand[y].bit_count()) # fewest candidates first
for bit in bits(cand[x]):
if len(found) >= limit:
break
trial = dict(cand)
trial[x] = bit
solve(trial, runs, limit, found)
return found
def count_solutions(cells, runs, limit=2):
"""0, 1, or `limit` (meaning "at least that many"). Stops as soon as it hits the limit."""
return len(solve({x: FULL for x in cells}, runs, limit))
Note limit=2. To check uniqueness you don’t need every solution, just to know whether a second one exists. The moment the search finds two, it stops. A badly ambiguous grid can have hundreds of solutions, and counting them all would tell you nothing extra.
Grading by Simulating a Human
Solve time says nothing about difficulty. The computer finishes the Hard grid in about 3 milliseconds; a person might need half an hour. Instead, grade the way How to Set Kakuro Difficulty does: apply techniques in order and record the hardest one needed.
- Pass A, run-level filtering, covers Tiers 1 and 2: magic blocks and intersections.
- Pass B, region counts, covers Tier 3. Pick a set of runs in one direction, add their clues, then compare with the clues of the crossing runs. Cells that only one direction covers have a known total.
- Anything left needs Tier 4 deductions (parity, chains) or guessing. Flag it for a human to look at.
Region counts compare across with down. Don’t hardcode 45; it only appears for a nine-cell run (see Mastering the 45 Rule).
# ------------------------------------------------------- region counting
def region_facts(runs, max_runs=3):
"""Across-vs-down counts: groups of 1-2 cells whose total the clues force.
For a set of runs in one direction, add their clues (the region total). Every
run in the other direction that touches the region either stays inside it or
pokes out. Pokes-out cells are outies; region cells the inside runs miss are innies.
"""
facts = []
across = [r for r in runs if r[2].startswith("across")]
down = [r for r in runs if r[2].startswith("down")]
for first, second in ((across, down), (down, across)):
for k in range(1, max_runs + 1):
for group in itertools.combinations(first, k):
region = {x for cells, _, _ in group for x in cells}
region_total = sum(total for _, total, _ in group)
touching = [r for r in second if region & set(r[0])]
covered = {x for cells, _, _ in touching for x in cells}
outies = covered - region
if 1 <= len(outies) <= 2:
facts.append((sorted(outies), sum(t for _, t, _ in touching) - region_total))
inside = [r for r in second if set(r[0]) <= region]
innies = region - {x for cells, _, _ in inside for x in cells}
if inside and 1 <= len(innies) <= 2:
facts.append((sorted(innies), region_total - sum(t for _, t, _ in inside)))
return facts
def apply_region_facts(cand, runs, facts):
"""Place one cell from a region count if all other cells in its group are known."""
for group, total in facts:
unknown = [x for x in group if cand[x].bit_count() > 1]
if len(unknown) != 1:
continue
known = sum(digit(cand[x]) for x in group if x not in unknown)
value = total - known
if 1 <= value <= 9 and cand[unknown[0]] & (1 << (value - 1)):
cand[unknown[0]] = 1 << (value - 1)
propagate(cand, runs)
return True
return False
On the Hard grid, one of these facts is the breakthrough from the difficulty article. The three left-hand across runs total 42, the four down runs through them total 59, and the two cells that poke out, r4c2 and r3c4, must add up to 17. Once r3c4 is known to be 9, apply_region_facts places r4c2 = 8, and filtering finishes the grid.
# ---------------------------------------------------------------- grading
def grade(text):
cells, runs = read_grid(text)
n = count_solutions(cells, runs)
if n != 1:
return f"rejected: {'no' if n == 0 else 'more than one'} solution"
cand = {x: FULL for x in cells}
propagate(cand, runs) # Pass A: magic blocks + intersections
if is_solved(cand):
return "Easy/Medium: run filtering solves it (Tiers 1-2)"
facts = region_facts(runs) # Pass B: across-vs-down region counts
while apply_region_facts(cand, runs, facts):
if is_solved(cand):
return "Hard: needs a region count (Tier 3)"
return "Expert or guessing: needs parity, chains, or search (Tier 4+)"
Pass A lumps Easy and Medium together. If you want to split them, one approach is to count how many cells magic blocks alone can place before any intersection is needed. That’s left as an extension; the grader above doesn’t do it.
The Generator Pipeline
Here’s the whole pipeline before the details. Each box is a function from the script:
Step 1: Layout
Start with the clue border, then add interior black cells in symmetric pairs, (r, c) and (N − r, N − c). Reject any layout with a one-cell run, a white cell missing its across or down run, or disconnected white cells. Designing a Kakuro Grid covers the rules. The script below takes a finished layout as input, written with # and . only:
# # # # # # #
# . . . . # #
# . . . . # #
# . . # . . #
# # . . # . .
# # # . . . .
# # # . . . .
Steps 2–4: Fill, Count, Repair
Fill the white cells with random digits, no repeats within a run, and add up the clues. Then count solutions.
Here’s the uncomfortable part: random fills almost never have one solution. Using this script on the series layout, all 300 of 300 random fills had at least two solutions. Uniform random digits produce middle-sized sums with many possible sets, and the layout’s eight 2x2 white blocks leave plenty of room for swaps.
Throwing fills away and trying again doesn’t fix that. Repairing them does. Change one random digit (keeping runs repeat-free), recount, and keep the change if the solution count didn’t go up. In the same test, this reached a single solution in 13 of 20 attempts, at about 10 seconds per attempt on a laptop. It’s how the series grid was made: the Draft became the Main grid by changing one digit, r5c3 from 9 to 4. How to Make Sure Your Kakuro Has Exactly One Solution shows why that change works.
# ------------------------------------------------------------- generating
def random_fill(cells, runs, rng, fixed=None):
"""Fill every white cell with 1-9, no repeats within a run, in random order.
`fixed` maps cells to digits that must stay as given (e.g. a hidden answer).
"""
runs_of = {x: [r[0] for r in runs if x in r[0]] for x in cells}
fixed = fixed or {}
fill = {}
def place(i):
if i == len(cells):
return True
x = cells[i]
used = {fill[y] for run_cells in runs_of[x] for y in run_cells if y in fill}
options = [d for d in range(1, 10) if d not in used]
if x in fixed:
options = [fixed[x]] if fixed[x] in options else []
rng.shuffle(options)
for d in options:
fill[x] = d
if place(i + 1):
return True
del fill[x]
return False
place(0)
return fill
def with_totals(runs, fill):
"""Recalculate every clue from the current digits."""
return [(cells, sum(fill[x] for x in cells), name) for cells, _, name in runs]
def repair(cells, runs, fill, rng, steps=400, limit=40, locked=()):
"""Change one digit at a time; keep the change if the solution count doesn't rise.
Cells in `locked` are never changed.
"""
runs_of = {x: [r[0] for r in runs if x in r[0]] for x in cells}
changeable = [x for x in cells if x not in locked]
score = count_solutions(cells, with_totals(runs, fill), limit)
for _ in range(steps):
if score == 1:
break
x = rng.choice(changeable)
used = {fill[y] for run_cells in runs_of[x] for y in run_cells if y != x}
options = [d for d in range(1, 10) if d not in used and d != fill[x]]
if not options:
continue
old, fill[x] = fill[x], rng.choice(options)
new_score = count_solutions(cells, with_totals(runs, fill), limit)
if new_score <= score:
score = new_score
else:
fill[x] = old
return score == 1
repair counts up to 40 solutions rather than 2, so it can tell “slightly ambiguous” from “wildly ambiguous” and move toward fewer. Both functions also take an optional set of cells to leave alone: fixed in random_fill and locked in repair. That lets you build a grid around digits you’ve already chosen, like a hidden code (Designing Kakuro Grids That Hide an Answer uses it).
Step 5: Grade
Run grade() on the finished puzzle and file it under the right label, or send it back for another fill if you were aiming for a different tier.
Practical Implementation: Running It
The last piece prints solutions and makes the file runnable from the command line:
def show(cells, solution):
rows = max(r for r, _ in cells) + 1
cols = max(c for _, c in cells) + 1
for r in range(rows):
print(" ".join(str(solution.get((r, c), "#")) for c in range(cols)))
if __name__ == "__main__":
for path in sys.argv[1:]:
with open(path, encoding="utf-8") as f:
text = f.read()
cells, runs = read_grid(text)
solutions = solve({x: FULL for x in cells}, runs, limit=2)
print(f"{path}: {len(solutions)} solution(s) found (search stops at 2)")
print(f" grade: {grade(text)}")
for s in solutions:
show(cells, s)
print()
Save the Main grid above as main.txt, plus the Draft and Hard grids:
draft.txt
# 16\ 12\ 10\ 8\ # #
\12 . . . . # #
\27 . . . . 21\ #
\3 . . 24\8 . . 6\
# \8 . . 17\8 . .
# # \21 . . . .
# # \27 . . . .
hard.txt
# 24\ 15\ 6\ 14\ # #
\17 . . . . # #
\13 . . . . 24\ #
\12 . . 11\12 . . 9\
# \10 . . 7\5 . .
# # \14 . . . .
# # \27 . . . .
Then run all three:
$ python kakuro.py main.txt draft.txt hard.txt
main.txt: 1 solution(s) found (search stops at 2)
grade: Easy/Medium: run filtering solves it (Tiers 1-2)
# # # # # # #
# 6 3 2 1 # #
# 9 6 8 4 # #
# 1 2 # 3 5 #
# # 1 7 # 6 2
# # # 4 8 3 1
# # # 8 9 7 3
draft.txt: 2 solution(s) found (search stops at 2)
grade: rejected: more than one solution
# # # # # # #
# 6 3 2 1 # #
# 9 6 8 4 # #
# 1 2 # 3 5 #
# # 1 7 # 6 2
# # # 8 9 3 1
# # # 9 8 7 3
# # # # # # #
# 6 3 2 1 # #
# 9 6 8 4 # #
# 1 2 # 3 5 #
# # 1 7 # 6 2
# # # 9 8 3 1
# # # 8 9 7 3
hard.txt: 1 solution(s) found (search stops at 2)
grade: Hard: needs a region count (Tier 3)
# # # # # # #
# 9 1 5 2 # #
# 7 2 1 3 # #
# 8 4 # 9 3 #
# # 8 2 # 4 1
# # # 1 3 8 2
# # # 8 4 9 6
That’s every expected result: Main has one solution and solves on filtering alone, Draft’s two solutions differ only in the four cells r5c3, r5c4, r6c3 and r6c4, and Hard has one solution but needs a region count. Each count_solutions call took about 1.4 ms for Main and 3 ms for Hard.
To generate new puzzles, save the blank layout above as layout.txt and add a small driver, generate.py, next to kakuro.py:
"""generate.py: fill a layout, repair it until unique, print the puzzle and its grade."""
import random
import sys
from kakuro import grade, random_fill, read_grid, repair, with_totals
def to_text(layout_text, runs):
"""Write each run's total into its clue cell, in down\\across notation."""
rows = [line.split() for line in layout_text.strip().splitlines()]
clues = {}
for cells, total, name in runs:
r, c = cells[0]
if name.startswith("across"):
clues.setdefault((r, c - 1), ["", ""])[1] = str(total)
else:
clues.setdefault((r - 1, c), ["", ""])[0] = str(total)
for (r, c), (down, across) in clues.items():
rows[r][c] = down + "\\" + across
return "\n".join(" ".join(f"{tok:<5}" for tok in row).rstrip() for row in rows)
if __name__ == "__main__":
with open(sys.argv[1], encoding="utf-8") as f:
layout = f.read()
seed = int(sys.argv[2]) if len(sys.argv) > 2 else 1
rng = random.Random(seed)
cells, runs = read_grid(layout)
for attempt in range(1, 11):
fill = random_fill(cells, runs, rng)
if repair(cells, runs, fill, rng):
puzzle = to_text(layout, with_totals(runs, fill))
print(f"unique after attempt {attempt}\n{puzzle}\ngrade: {grade(puzzle)}")
break
else:
print("no unique puzzle in 10 attempts; try another seed or a layout with shorter runs")
$ python generate.py layout.txt 1
unique after attempt 1
# 13\ 16\ 12\ 23\ # #
\21 . . . . # #
\13 . . . . 28\ #
\17 . . 18\17 . . 11\
# \12 . . 4\11 . .
# # \23 . . . .
# # \11 . . . .
grade: Easy/Medium: run filtering solves it (Tiers 1-2)
That run took about 10 seconds. A different seed gives a different puzzle, and some seeds need a second or third attempt.
Best Practices
Do:
- ✓ Filter runs by digit set before every guess.
- ✓ Stop counting at 2 solutions when checking uniqueness.
- ✓ Grade with human-style passes, not timing.
- ✓ Test your solver on a grid you know has two solutions, like
draft.txt, not just ones that work.
Don’t:
- ✗ Rely on forward checking alone.
- ✗ Publish generated puzzles without a solution count.
- ✗ Hardcode grid sizes. Nothing in this script assumes 7x7.
Troubleshooting
The generator never finds a unique fill.
Uniform random digits produce mid-range sums with many possible sets, and large white areas leave room for swaps. Repair fills one digit at a time instead of starting over, and give repair more steps. If a layout still won’t settle, add black cells to shorten its longest runs.
The solver says a generated grid has no solution.
The clue calculation and the solver disagree about which cells belong to a run. Build runs in one place, as read_grid does here, and use the same list for both calculating clues and solving.
Off-by-one digits everywhere.
Mixing up bit positions and digits (digit 1 is bit 0, not bit 1) shifts every answer. Keep the conversion in one place, like digit() and the 1 << (d - 1) in the combination table, and never convert inline.
propagate is slow on big grids.
fits tries placements recursively, which is fast for runs of up to five or six cells but grows quickly for long runs. For 15x15 grids with nine-cell runs, cache fits results per run between passes, or skip re-filtering runs whose cells haven’t changed.
What You’ve Built
Kakuro is NP-complete in general, but published grids solve in milliseconds with the right pruning. Combination tables plus run-level filtering do most of the work, and backtracking only has to cover what’s left. Count solutions and stop at two. Repair random fills one digit at a time instead of throwing them away. And grade by the hardest human technique needed, not by how long the computer took.
Run the script on the three series grids, then try generate.py with a few seeds. Next, Designing Kakuro Grids That Hide an Answer uses fixed and locked to build a grid around a code you choose.
The Kakuro Puzzle Design series:
- How to Make a Kakuro Puzzle
- How to Make Sure Your Kakuro Has Exactly One Solution
- How to Set Kakuro Difficulty
- Designing Kakuro Grids That Hide an Answer