vøiddo
← blog  /  tools

Futoshiki generator in Python: signs alone often are not enough

2026-11-14  ·  5 min read  ·  tools

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.

A futoshiki is a Latin square, each row and column holding 1 to n once, with < and > signs between some squares that sit side by side, and sometimes a few starting digits. A Python generator draws a square and keeps some of its signs. The question it has to answer is how many, and which.

On 31 October 2026 we measured that on random 5 x 5 squares, the size of an easy book puzzle.

The short version#

  • Few random signs: 5 or 10 random signs and no digits gave a puzzle with one answer in 0 of 40 squares; 15 signs in 1 of 40.
  • Every sign: all 40 signs and no starting digit gave one answer in only 26 of 40 squares. In the other 14, the signs between neighbours could not tell two squares apart.
  • The fix: start from all the signs, add starting digits from the square until exactly one answer is left, then take signs away one at a time, keeping each removal only if one answer is still left. On average that left 7.1 signs and 3.1 starting digits, in about 0.3 s a puzzle.

The code#

A futoshiki generator that keeps exactly one answerpython
import random


def latin_square(n, rng=random):
    """Random rows, each kept only if it clashes with no row above it; start over when stuck."""
    rows = []
    while len(rows) < n:
        for _ in range(5000):
            row = rng.sample(range(1, n + 1), n)
            if all(row[c] != above[c] for above in rows for c in range(n)):
                rows.append(row)
                break
        else:
            rows = []
    return rows


def all_signs(square):
    """Every sign the square allows: ((r, c), (r2, c2)) means the first square holds the smaller digit."""
    n, out = len(square), []
    for r in range(n):
        for c in range(n):
            for r2, c2 in ((r, c + 1), (r + 1, c)):
                if r2 < n and c2 < n:
                    a, b = (r, c), (r2, c2)
                    out.append((a, b) if square[r][c] < square[r2][c2] else (b, a))
    return out


def count_answers(n, signs, givens=None, stop=2):
    """How many squares keep every sign and starting digit (stops at `stop`); square by square, smallest choice first."""
    givens = givens or {}
    grid, found = {}, [0]
    cells = [(r, c) for r in range(n) for c in range(n)]

    def ok(cell, v):
        r, c = cell
        if any(grid.get((r, x)) == v for x in range(n)) or any(grid.get((y, c)) == v for y in range(n)):
            return False
        for small, big in signs:
            if small == cell and big in grid and not v < grid[big]:
                return False
            if big == cell and small in grid and not grid[small] < v:
                return False
        return givens.get(cell, v) == v

    def go(i):
        if found[0] >= stop:
            return
        if i == len(cells):
            found[0] += 1
            return
        for v in range(1, n + 1):
            if ok(cells[i], v):
                grid[cells[i]] = v
                go(i + 1)
                del grid[cells[i]]

    go(0)
    return found[0]


def make(n, rng=random):
    """A square, signs and starting digits with exactly one answer: start from every sign, add starting digits until
    one answer is left (signs alone are often not enough), then take signs away while it stays one."""
    square = latin_square(n, rng)
    signs, givens = all_signs(square), {}
    cells = [(r, c) for r in range(n) for c in range(n)]
    rng.shuffle(cells)
    while count_answers(n, signs, givens) > 1:
        r, c = cells.pop()
        givens[r, c] = square[r][c]
    for s in rng.sample(signs, len(signs)):
        signs.remove(s)
        if count_answers(n, signs, givens) != 1:
            signs.append(s)
    return square, signs, givens
Run itpython
square, signs, givens = make(5, random.Random(1))
print(len(signs), "signs,", len(givens), "starting digits, answers:", count_answers(5, signs, givens))

With that seed it kept 10 signs and 2 starting digits, with one answer.

Why every sign is not always enough#

A sign only compares two neighbours. Two different squares can agree on every one of those 40 comparisons, so nothing but a digit tells them apart. That happened in 14 of our 40 squares, which is why make() adds digits first instead of hoping the signs will do.

Taking signs away#

Once one answer is left, most signs are not needed. make() tries removing each sign in random order and puts it back if a second answer appears. What is left are signs that each matter: from none to 12 in our runs. The starting digits are not trimmed afterwards: in 11 of 40 puzzles at least one of them could go and still leave one answer. Trimming them the same way is a short loop.

count_answers() is a plain search that stops at 2. At 5 x 5 a whole puzzle, with every search make() runs, takes about 0.3 s. At 6 x 6, two of three runs of make() took between 4 and 13 s and the third more than 90 s, so for 6 x 6 and 7 x 7 books a generator needs a smarter solver.

One answer is not the whole job, either. A book also grades how a puzzle can be solved, step by step, without guessing; that takes a second solver that works the way a person does.

A whole book, not one grid#

Our futoshiki book maker makes both checks on every puzzle: a separate search, apart from the steps that make the puzzles, finds exactly one finished grid for its signs and starting digits, and each puzzle is solved again step by step with no guessing, with harder steps only at the harder levels. Easy books use 5 x 5 grids, medium 6 x 6 and hard 7 x 7, and the book is checked against KDP's paperback specs before you can download it. One futoshiki book costs 500 credits, from $3.30 in the big pack.

written

keep reading