← blog  /  tools

Jigsaw sudoku generator in Python: odd shapes need fewer digits

2026-11-20  ·  7 min read  ·  tools

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#

A jigsaw sudoku generator: shapes, a filled grid, a puzzle with one answerpython
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, puzzle
Run itpython
r5 = 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:

Shapes and puzzletext
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