• 14 Sep. 2026
• sudoku
• recreational-math

14 min read

There are only twelve 4x4 sudokus! ... Or 288, depending on what counts as different solutions to you.

Today's rabbithole is how many unique 4x4 sudoku solutions (as well as possible puzzles) there are. Why? I don't know, the question just popped into my mind and I think its answer is mildly interesting.

If you're not familiar, a 4x4 sudoku is a 4x4 grid divided in rows, columns, and 2x2 boxes, with the goal of filling each cell with a digit from 1 to 4 such that in every row, column, and box, every digit appears exactly once.

╔═══╤═══╦═══╤═══╗
║   │   ║   │   ║
╟───┼───╫───┼───╢
║   │   ║   │   ║
╠═══╪═══╬═══╪═══╣
║   │   ║   │   ║
╟───┼───╫───┼───╢
║   │   ║   │   ║
╚═══╧═══╩═══╧═══╝

This is actually a smaller case of the more standard 9x9 sudoku (which is similarly divided in 3x3 boxes). This generalizes to $N \times N$

Normally these puzzles start from a partially filled grid (as finding a solution for an empty grid is easy). However, only for the time being, we will consider "solutions" to be any valid filling, from an empty starting position.

For example, here are three distinct valid solutions to a 4x4 sudoku:

       (A)
╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 2 │ 1 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

       (B)
╔═══╤═══╦═══╤═══╗
║ 2 │ 1 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 1 │ 2 ║
╟───┼───╫───┼───╢
║ 1 │ 2 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

       (C)
╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╚═══╧═══╩═══╧═══╝

If we look closer to the given solutions, we notice that they're not all "distinct" in the same way. Solution (B) is actually just solution (A) with all the 1s swapped with 2s and viceversa.

In the context of a normal sudoku (i.e: not a variant sudoku) the digits we use to fill the grid are just meaningless symbols. If we wanted, we could solve the same puzzle using "🔴, 🟣, 🔵, 🟢" instead of "1, 2, 3, 4", and the puzzle would remain exactly the same. Similarly, if instead of swapping numbers for colored shapes we swapped digits with digits, the puzzle remains the same.

Under this light, we can understand solutions (A) and (B) as using different symbols for the same puzzle: they have the same underlying structure. Viceversa, (A) and (C) are structurally different: no matter how many digits we swap, in solution (A) the cells at row-2-column-1 and row-1-column-4 contain the same symbol, while in solution (C) the same cells contain different symbols.

So the question we are asking is:

How many 4x4 sudoku solutions exist? And of these solutions, how many are actually distinct (structurally)?

We start with the easy question : how many 4x4 sudoku solutions exist, potentially with the same structure? Luckily the numbers we are dealing with are quite small, meaning that we can solve this question by bruteforce in a fraction of a second.

The (naive) way to do it is to start with an empty grid, and for each cell figure out the remaining possible values, exploring each possible value recursively in a depth-first way:

CodeHelpers

python

N = 4

def findSolutions(sudoku: list[int], curr: int) -> list[list[int]]:
    if curr == N**2: # No cells remaining to be filled, solution found
        return [sudoku]

    # All the cells to check: cells in same row, cells in same column, cells in same square.
    _cells2Check = sameRowCells[curr] + sameColCells[curr] + sameBoxCells[curr]
    # Only check cells with indices lower than i, as the other are not yet set.
    cells2Check = {other for other in _cells2Check if other < curr}
    othersValues = {sudoku[other] for other in cells2Check}
    allowedValues = {value for value in range(1, N + 1) if not value in othersValues}

    if len(allowedValues) == 0: # No valid digit, so no valid solution. Return empty
        return []

    solutions = []
    for value in allowedValues:
        newSudoku = sudoku.copy()
        newSudoku[curr] = value
        solutions += findSolutions(newSudoku, curr + 1)
    return solutions


emptySudoku = [0] * (N**2)
allSolutions = findSolutions(emptySudoku, 0)
print("Number of total solutions:", len(allSolutions))

python

SQRT_N = int(math.sqrt(N))

def _index2pos(i: int) -> tuple[int, int]:
    return (i % N, i // N)

def _pos2index(x: int, y: int) -> int:
    return x + y * N

def _sameRowCells(i: int) -> list[int]:
    (_, y) = _index2pos(i)
    return [_pos2index(cx, y) for cx in range(N)]

def _sameColCells(i: int) -> list[int]:
    (x, _) = _index2pos(i)
    return [_pos2index(x, cy) for cy in range(N)]

def _sameBoxCells(i: int) -> list[int]:
    (x, y) = _index2pos(i)

    # x & y coords of the BOX where cell of index i is
    bx = x // SQRT_N
    by = y // SQRT_N
    return [
        _pos2index(bx * SQRT_N + cx, by * SQRT_N + cy)
        for cx in range(SQRT_N)
        for cy in range(SQRT_N)
    ]

# Precompute all possible values for efficiency
sameRowCells = {i: _sameRowCells(i) for i in range(N**2)}
sameColCells = {i: _sameColCells(i) for i in range(N**2)}
sameBoxCells = {i: _sameBoxCells(i) for i in range(N**2)}

In roughly half a second this code should output

Number of total solutions: 288

Only 288 possible solutions! A miniscule number compared to the 6,670,903,752,021,072,936,960 possible solutions for 9x9 standard sudoku, which is the next possible step at $n=3$

At the same time, with some horribly inaccurate napkin math, we can give an extremely rough approximation of the number of possible solutions in function of $N$: if we ignore the column and box constraint and consider only the row constraint, then every row has $N!$ possible combinations, and there are $N$ rows, making the total number of possible combinations $N!^N = (n^2!)^{n^2}$

Note that this is a terrible upperbound: if we use this formula for $n=3$

Still, $n=2$

Now we want to count actually distinct solutions, that is the distinct structures that a solution can have.

We have already seen that given any solution, we can apply any permutation of the digits 1, 2, 3, 4 to get a new solution. Since there are 4! = 24 such permutations, this means that every structure is overcounted by a factor of 24. So in theory the number of actually distinct solutions should be

288 / 24 = 12 distinct solutions

There is another way to approach this question, one that allows us to reuse the terrible python code from before. The key facts are the following:

• We are considering the digits as just symbols. We don't care what they actually are, they could be anything, and any permutation of them is valid
• In any given solution, the first row (like any other row) is guaranteed to contain four distinct symbols

Then, the idea is the following: given any solution structure, let's call the first symbol of the first row 1, the second symbol of the first row we'll call 2, and so on for 3 and 4. This way, we can represent every structure with the corresponding solution which starts with 1 2 3 4 in the first row.

Notice that if two different solutions $S_1, S_2$

1. if they had the same structure, then there should be a permutation of digits $\sigma$ such that if we apply $\sigma$ to $S_1$
2. however, if $\sigma$ swaps any digit then when we apply it to $S_1$
3. similarly, if $\sigma$ leaves all the digit as they were, when we apply $\sigma$ to $S_1$
4. hence, such a $\sigma$ cannot exist and the two solutions must be structurally different.

This gives a 1-to-1 correspondence between the distinct possible structures and the possible solutions starting with 1 2 3 4. So, to get the number of all possible structures, we can just count all the possible solutions starting with 1 2 3 4. To count these, we just need to initialize the emptySudoku in our code to start with 1 2 3 4:

python

emptySudoku = [0] * (N**2)
emptySudoku[0:N] = [value for value in range(1, N + 1)]

distinctSolutions = findSolutions(emptySudoku, N)
print("Number of distinct solutions:", len(distinctSolutions))

# Note: if we have previously computed allSolutions, then instead of computing
# distinctSolutions from scratch, we can just take all the solutions that start
# with `1 2 ... N` from allSolutions, as follows:
# ```python
# distinctSolutions = [sol for sol in allSolutions if sol[0:N] == list(range(1, N + 1))]
# ```

If we run this, we get...

Number of distinct solutions: 12

Hurray! Our terrible python code gives us the same result we expect from the theory. Here are all the possible distinct solutions up to permutations of the digits:

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 3 ║ 4 │ 1 ║
╟───┼───╫───┼───╢
║ 4 │ 1 ║ 2 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 4 │ 1 ║ 2 │ 3 ║
╟───┼───╫───┼───╢
║ 2 │ 3 ║ 4 │ 1 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 4 │ 3 ║ 2 │ 1 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 4 │ 3 ║ 1 │ 2 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 2 │ 1 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 3 │ 4 ║ 1 │ 2 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 4 ║ 1 │ 3 ║
╟───┼───╫───┼───╢
║ 3 │ 1 ║ 4 │ 2 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 1 ║ 4 │ 2 ║
╟───┼───╫───┼───╢
║ 2 │ 4 ║ 1 │ 3 ║
╚═══╧═══╩═══╧═══╝

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╠═══╪═══╬═══╪═══╣
║ 3 │ 4 ║ 1 │ 2 ║
╟───┼───╫───┼───╢
║ 2 │ 1 ║ 4 │ 3 ║
╚═══╧═══╩═══╧═══╝

Until now we have ignored a crucial part of sudoku puzzles: the initial configuration. Sudoku puzzles start with some set of digits already filled in, such as the following grid:

╔═══╤═══╦═══╤═══╗
║ 1 │   ║   │   ║
╟───┼───╫───┼───╢
║   │ 4 ║   │   ║
╠═══╪═══╬═══╪═══╣
║   │   ║   │ 3 ║
╟───┼───╫───┼───╢
║   │   ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

and the puzzle consists in filling the rest of the grid. In general, it is required that the partial filling has exactly one solution: for example, a grid with only one digit placed is not a valid puzzle, as there are many possible ways to fill the rest of the grid starting from only one digit placed.

We want to count how many such puzzles (partially filled grids) exist. Before we start, a precisation: we want to discard uniteresting puzzles. For example, the following puzzle is uninteresting:

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ 3 │   ║ 1 │ 2 ║
╠═══╪═══╬═══╪═══╣
║ 2 │ 1 ║ 4 │ 3 ║
╟───┼───╫───┼───╢
║ 4 │ 3 ║ 2 │ 1 ║
╚═══╧═══╩═══╧═══╝

While it's true that it is partially filled and it has a unique solution, it is not minimal: we could have obtained the exact same unique solution with fewer digits.

So we are interested only in minimal puzzles: a puzzle is minimal if by removing any of the given digits, the solution becomes not unique.

How many 4x4 minimal sudoku puzzles exist?

We can find the answer with some more terrible bruteforcing python code. The idea is the following:

1. We loop through every possible solution, and for each solution we loop through every possible subset of cells (which will be the given digit in the puzzle)
2. For each subset, we check which other solutions agree on that subset. That is, we find all the possible solutions given that subset of known digits.
3. If it's not the case that the current solution is the only possible solution, discard the subset (as it does not lead to a unique solution, so it's not a valid puzzle)
4. Otherwise, check if it's minimal (by checking if there are other puzzles that are a sub-subset of this subset of cells). If it's minimal, add it to the list.

python

allPuzzles = 0
for k, solution in enumerate(allSolutions):
    cellToPosibleSolutions = [
        # For each cell c, precompute all the solutions that have value solution[c] in cell c
        {j for (j, other) in enumerate(allSolutions) if (other[c] == solution[c])}
        for c in range(N**2)
    ]

    puzzles: list[int] = []

    # Iterate on all possible subsets
    for subsetMask in range(1, 2 ** (N**2)):
        subset = {i for i in range(N**2) if (subsetMask & (1 << i))}
        possibleSolutions = set.intersection(
            *[cellToPosibleSolutions[i] for i in subset]
        )

        if possibleSolutions != {k}: # the current solution (k) is NOT the only possible. Skip
            continue

        isMinimal = True
        for other in puzzles:
            if subsetMask & other == other:
                isMinimal = False
                break

        if isMinimal:
            puzzles.append(subsetMask)

    allPuzzles += len(puzzles)

print("Number of possible puzzles:", allPuzzles)

If you run the code above you get (after a painful 2 to 3 minutes...) that the number of possible puzzles is 85632, but I think that the interesting part is how we found them.

First of all, we need to iterate on all the subsets of the solutions. While python does not have natively a function to create an iterator of the subset of any given list, we can do it ourself by expressing the subset as a bitmask: given a list of elements and a subset, for each element we assign 0 if the element is not present in the subset, and 1 if it is present. This gives a binary representation of the subset. Crucially, if the original list was of size $S$, we are assigning exactly $S$ bits, so the binary number corresponding to the subset will be betweeen $0$ and $2^S-1$

The actual cool trick is the following: recall that we had to make sure that any accepted puzzle is minimal, meaning that there does not exist any other puzzle that is a subset of the current puzzle. This is close to what we are doing in the code, with a subtle difference: in the code, in order to accept a puzzle, we are only checking that no previously seen puzzle is a subset of the current one. We are checking against only the puzzles we know of, not all the possible puzzles.

This is, however, equivalent! Suppose for example that we find a puzzle $P$ which is a valid puzzle, but it is not minimal. This means that there's another puzzle $Q$ which is a subset of $P$. If that's the case, wherever the bitmask of $Q$ had a 1, the bitmask of $P$ must also have a 1. This gives us an efficient way of checking "subset-ness" via bitmask, with bit operations: bitmask(P) & bitmask(Q) == bitmask(Q). But crucially, this also means that bitmask(Q) is a number smaller than bitmask(P). Given the order on which we are iterating, this means that by the time we got to $P$ we have also already iterated on all the possible sub-subsets of $P$, so checking against only the "already seen" is equivalent to checking against all the possible sub-subsets!

Similarly, you can apply the same trick if you're looking for maximal subsets instead of minimal subsets. To check if some subset $Q$ is a superset of $P$, the check becomes bitmask(P) & bitmask(Q) == bitmask(P), and the order of iteration must be reversed.

No.

We could just run the code with $n=3$

$O(2^{N^2 \cdot N!})$

We are lucky that it ran in a reasonable time for $n=2$

If you look it up online you will find that the number of possible puzzles in the 9x9 case is not known (some upper and lower bounds have been given).

There are only 12 distinct 4x4 solutions! 288 if you don't mind permutations! And only 85632 possible starting positions, which becomes only 3568 if you count them up to permutations!

If you print them on A4 pages at 4cm size (which I find comfortable, but you could go smaller) that's only 102 pages for the up-to-permutations, and 2247 pages for every possible 4x4 puzzle ever!

If you solved a page a day (and I reckon you could solve one in ~30s once you get up to speed, so less than 20 minutes per page), you would solve every possible 4x4 in less then 7 years (or 102 days for the up-to-permutations).

And then you could go around saying "I've done the 4x4 sudokus". Like, all of them.

Should you? I don't know. Maybe? There are worse ways of spending 20 minutes a day, it is a bit of light mental exercise, it can be relaxing and somewhat meditating if you get in the flow. And you could go around saying "I've done the 4x4 sudokus".

Also, I find these numbers mildly interesting but maybe we should have expected similar numbers. After all, a 4x4 sudoku is not that complex, and the only step below it (2x2 sudokus) is trivial, so maybe this result is not surprising. At the same time, there are plenty of books and apps being sold for playing on 4x4 sudokus, which makes it kind of weird that there are only 288 possible solutions.

Not all the solutions are made equal. Most of them (192 out of 288) have 304 minimal puzzles that solve to them, but a decent chunk (96 out of 288) only has 284 minimal puzzle corresponding to them. Why is that? What is it about the structure that makes some of the solutions have more puzzles, and some less?

As we said, there are 12 distinct solutions, meaning 12 = 3x2x2. Keeping the first row fixed (which is what allows us to count the distinct structures) to 1 2 3 4, this 3x2x2 seems to hint at the fact that it might be possible to find three cells in the grid, one with 3 possible digits and two with 2 possible digits (all independent of eachother) that once set uniquely identify the solution.

This is... almost the case, but not quite, and I can't find a way to make it into an elegant argument.

For example, let's see the case for three cells that look like to be somewhat independent: r2c1, r3c3, r4c2

╔═══╤═══╦═══╤═══╗
║ 1 │ 2 ║ 3 │ 4 ║
╟───┼───╫───┼───╢
║ ▒ │   ║   │   ║
╠═══╪═══╬═══╪═══╣
║   │   ║ ▒ │   ║
╟───┼───╫───┼───╢
║   │ ▒ ║   │   ║
╚═══╧═══╩═══╧═══╝

Indeed, r2c1 has two possible values (3, 4), which accounts for a factor of 2 in the total of 12, and r3c3 has three possible values (1, 2, 4) all possible independently of the value chosen for r2c1, and this accounts for a factor of 3 in the total of 12. However, the case of r4c2 is a bit more complicated.

For example, if we chose r3c3 = 2 then r4c2 can be either 1 or 3 (both of which lead to unique solutions), but if we choose r3c3 = 1, then r4c2 is forced to also be a 1. The case for r3c3 = 4 is even worse! If we choose r3c3 = 4 and r2c1 = 3, then r4c2 has two possible values (1 and 3), but picking 3 does not lead to a unique solution!

We can, for sure, procede in a tree-like fashion, deciding the value of one cell, then another, then another, and show that there are a total of twelve leaves, but which cell we pick next depends on which branch we are on, which makes for an extremely messy argument, annoying to write up.

In the terrible code above, we iterated over all the possible subsets in order to find puzzles. This is, however, incredibly wasteful. For example, if a subset has less than $N-2$

Similarly, if the subset is too big, than it's very likely not to be minimal. The problem is what counts as "too big". For example, in the 9x9 case there are puzzles with 40 or 41 digits, meaning that to be safe the upper bound for the size of the subset should be at least $N^2 / 2$

Once we have decided on upperbound and lowerbound on the number of cells in the subset, we can filter for those as follows:

python

masks = [i for i in range(2 ** (N**2)) if lowerBound <= i.bit_count() <= upperBound]
for subsetMask in masks:
    # [...]

Repository with terrible python code: github.com/Fran314/how-many-4x4-sudokus

Puzzles and solutions (CSV):

Puzzles and solutions (txt/ascii):

Puzzles and solutions (txt/unicode):

puzzles-with-solutions.tar.gz (tar.gz, 694 KB)