Jigsaw sudoku generator in Python: odd shapes need fewer digits
The same generator that leaves 24 starting digits in a plain sudoku left 17 when the boxes became irregular shapes. The catch: for some shapes the search found no grid at all, and making a puzzle took over 100 times longer.
A jigsaw sudoku, also called irregular sudoku, keeps the rows and columns of a sudoku and swaps the nine 3 x 3 boxes for nine irregular shapes of nine squares each. A generator needs three things: shapes, a filled grid that fits them, and a puzzle with exactly one answer.
On 31 October 2026 we built them in Python and compared the puzzles with the same generator on plain boxes, as in our sudoku generator post.
The short version#
- Shapes: start from the nine boxes and trade squares between neighbouring shapes, two at a time, while both stay in one piece and inside 5 rows and 5 columns. 300 trades took 27 ms a layout. In 4 of 200 layouts two or more plain boxes survived, which a book should reject.
- A filled grid does not always exist. With 10 random starts of 20,000 steps each, the search found a grid for 94 of 100 random layouts. In another run it found none for 8 of 30. The generator simply draws new shapes.
- Fewer starting digits: taking digits away in random order while the answer stays unique left 17.3 on average (15 to 20) with jigsaw shapes, against 24.2 (22 to 27) with plain boxes.
- Slower: that took 27 s a puzzle (median) with jigsaw shapes and 0.2 s with plain boxes.
The code#
import random
N = 9
def one_piece(cells):
cells = set(cells)
todo = [next(iter(cells))]
seen = set(todo)
while todo:
r, c = todo.pop()
for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if nb in cells and nb not in seen:
seen.add(nb)
todo.append(nb)
return len(seen) == len(cells)
def shapes(rng=random, trades=300, box=5):
"""Start from the nine 3 x 3 boxes and trade squares between neighbouring shapes, two at a time so every shape
keeps nine, as long as both stay in one piece and inside `box` rows and columns."""
region = [[(r // 3) * 3 + c // 3 for c in range(N)] for r in range(N)]
def cells(g):
return [(r, c) for r in range(N) for c in range(N) if region[r][c] == g]
def fits(g):
cs = cells(g)
return (one_piece(cs) and max(r for r, c in cs) - min(r for r, c in cs) < box
and max(c for r, c in cs) - min(c for r, c in cs) < box)
def border(a, b):
"""Squares of shape a that touch shape b."""
return [(r, c) for r, c in cells(a) if any(0 <= r + dr < N and 0 <= c + dc < N and region[r + dr][c + dc] == b
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)))]
done = 0
while done < trades:
r, c = rng.randrange(N), rng.randrange(N)
dr, dc = rng.choice(((0, 1), (1, 0), (0, -1), (-1, 0)))
if not (0 <= r + dr < N and 0 <= c + dc < N) or region[r][c] == region[r + dr][c + dc]:
continue
a, b = region[r][c], region[r + dr][c + dc]
region[r][c] = b # one square from a to b ...
back = [x for x in border(b, a) if x != (r, c)]
if back:
y = rng.choice(back)
region[y[0]][y[1]] = a # ... and one from b to a
if fits(a) and fits(b):
done += 1
continue
region[y[0]][y[1]] = b
region[r][c] = a
return region
def solutions(region, grid, stop=2, rng=None, limit=200000):
"""Fill the zeros of `grid` (9 x 9 lists): count solutions up to `stop`, square with fewest options first.
With `rng`, digits are tried in random order and the first solution is returned as a grid instead.
Gives up after `limit` steps and returns None."""
grid = [row[:] for row in grid]
rows, cols, regs = [0] * N, [0] * N, [0] * N
for r in range(N):
for c in range(N):
if grid[r][c]:
bit = 1 << grid[r][c]
if (rows[r] | cols[c] | regs[region[r][c]]) & bit:
return 0
rows[r] |= bit
cols[c] |= bit
regs[region[r][c]] |= bit
empty = [(r, c) for r in range(N) for c in range(N) if not grid[r][c]]
found, steps = [0], [0]
def go():
steps[0] += 1
if steps[0] > limit:
raise TimeoutError
best, options = None, None
for r, c in empty:
if not grid[r][c]:
free = [d for d in range(1, 10) if not (rows[r] | cols[c] | regs[region[r][c]]) & (1 << d)]
if best is None or len(free) < len(options):
best, options = (r, c), free
if len(free) <= 1:
break
if best is None:
found[0] += 1
return found[0] >= stop
r, c = best
if rng:
rng.shuffle(options)
for d in options:
bit = 1 << d
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
regs[region[r][c]] |= bit
if go():
return True
grid[r][c] = 0
rows[r] &= ~bit
cols[c] &= ~bit
regs[region[r][c]] &= ~bit
return False
try:
go()
except TimeoutError:
return None
if rng:
return grid if found[0] else 0
return found[0]
def fill(region, rng=random, restarts=10, limit=20000):
"""A filled grid for these shapes, or None. A random search can wander into a dead end for a long time, so it
starts again, up to `restarts` times, after `limit` steps."""
for _ in range(restarts):
full = solutions(region, [[0] * N for _ in range(N)], stop=1, rng=rng, limit=limit)
if full == 0:
return None # proved: no grid fits these shapes
if full:
return full
return None
def make(region, rng=random):
"""A filled grid for these shapes, then take digits away in random order while the answer stays unique."""
full = fill(region, rng)
if not full:
return None
puzzle = [row[:] for row in full]
for r, c in rng.sample([(r, c) for r in range(N) for c in range(N)], N * N):
keep, puzzle[r][c] = puzzle[r][c], 0
if solutions(region, puzzle) != 1:
puzzle[r][c] = keep
return full, puzzler5 = random.Random(5)
while True:
region = shapes(r5)
made = make(region, r5)
if made:
break
full, puzzle = made
for shape_row, row in zip(region, puzzle):
print("".join(str(s) for s in shape_row), " ", "".join(str(d) if d else "." for d in row))
print("starting digits:", sum(map(bool, sum(puzzle, []))), "| solutions:", solutions(region, puzzle))With that seed it printed the shapes (the digit in each square is its shape) next to the puzzle, 18 starting digits with one solution:
001111122 .1.4.....
000111222 .....3...
000122255 .....21..
034444255 4..3..71.
634344455 ...9.....
633338455 ....8..9.
663378858 ......9.6
667777888 67.......
666777788 .54......Why odd shapes need fewer digits#
We did not test why. A likely reason: in a plain sudoku, rows, columns and boxes line up in bands of three, which leaves more ways for digits to trade places, and starting digits are needed to stop that. Irregular shapes break those bands up. The generator does not aim for few digits; it takes away every digit it can, and with jigsaw shapes it can take away about seven more.
Why it gets slow#
solutions() is a plain search: fill the square with the fewest options, back up on a dead end. It runs once for every digit make() tries to take away. With jigsaw shapes all those runs together took over 100 times longer (27 s against 0.2 s), and a search for a filled grid could wander for 20,000 steps without finding one, which is why fill() starts again instead of searching on. A faster solver, such as Knuth's Algorithm X, pays off here.
The generator also does not grade puzzles. One answer is not the same as an answer a person can reach step by step, and a book needs both.
A whole book, not one grid#
Our jigsaw sudoku book maker gives every puzzle shapes of its own: each one nine squares joined side to side that fits inside 5 rows and 5 columns, at least eight of the nine different from a 3 x 3 box, and no two puzzles in a book with the same shapes. A second program, written apart from the one that makes the puzzles (Knuth's Algorithm X), counts the solutions with that puzzle's rows, columns and shapes, finds exactly one, and checks it against the answer printed at the back.
Easy and medium puzzles are solved square by square with singles, and easy ones start with 36 digits or more; hard ones need locked candidates or pairs, and nothing harder goes in a book. Each book is checked against KDP's paperback specs before you can download it. One jigsaw sudoku book costs 500 credits, from $3.30 in the big pack.
written
5 min readKDP margins and gutter: check your PDF before you upload it
KDP's inside margin grows with the page count, and a book of 151 pages needs more than one of 150. The table from KDP's help, and forty lines of Python that find the text too close to an edge.
5 min readFutoshiki generator in Python: signs alone often are not enough
A 5 x 5 futoshiki has 40 places for a sign. Even with all 40 filled in, 14 of our 40 squares still had more than one answer. A generator that adds starting digits first and then removes signs gets there in 0.3 s.
19 min readKDP coloring book size and bleed: check your interior PDF in Python
The trim sizes KDP lists, when a coloring book needs bleed, why the page count doubles and what 300 ppi means. Then a Python check that reads your interior PDF and says where it breaks KDP's published rules.