There are only twelve 4x4 sudokus - and a cool trick for finding minimal subsets

14 Sep. 2026sudokurecreational-math14 min readThere are only twelve 4x4 sudokus! ... Or 288, depending on what counts as different solutions to you.What, why, and exactly whatToday'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×NN \times N sudokus where N=n2N = n^2 for some integer nn. For n=2n=2 we get 4x4 sudokus, and the next step is n=3n=3 with 9x9 sudokus.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)?Initial answers, and some terrible python codeWe 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:CodeHelperspythonN = 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))pythonSQRT_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 outputNumber of total solutions: 288Only 288 possible solutions! A miniscule number compared to the 6,670,903,752,021,072,936,960 possible solutions for 9x9 standard sudoku[1], which is the next possible step at n=3n=3![2]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 NN: if we ignore the column and box constraint and consider only the row constraint, then every row has N!N! possible combinations, and there are NN rows, making the total number of possible combinations N!N=(n2!)n2N!^N = (n^2!)^{n^2}.Note that this is a terrible upperbound: if we use this formula for n=3n=3 we get ≈1050\approx 10^{50}, way above the correct answer of ≈6.6×1021\approx 6.6 \times 10^{21}Still, n=2n=2 small, n=3n=3 big!Counting actually distinct solutionsNow 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 be288 / 24 = 12 distinct solutionsThere 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 validIn any given solution, the first row (like any other row) is guaranteed to contain four distinct symbolsThen, 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 S1,S2S_1, S_2 start both with 1 2 3 4, then they must also be structurally different:if they had the same structure, then there should be a permutation of digits σ\sigma such that if we apply σ\sigma to S1S_1 we get S2S_2however, if σ\sigma swaps any digit then when we apply it to S1S_1 we will get a solution that does not start with 1 2 3 4, so it cannot be equal to S2S_2similarly, if σ\sigma leaves all the digit as they were, when we apply σ\sigma to S1S_1 the result is exactly S1S_1, which by assumption is not equal to S2S_2hence, 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:pythonemptySudoku = [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: 12Hurray! 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 ║ ╚═══╧═══╩═══╧═══╝ ╔═══╤═══╦═══╤═══╗