There are only twelve 4x4 sudokus - and a cool trick for finding minimal subsets | baldino.dev
baldino.dev > BlogThere are only twelve 4x4 sudokus - and a cool trick for finding minimal subsets14 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 NN×N sudokus where N=n2N = n^2N=n2 for some integer nnn. For n=2n=2n=2 we get 4x4 sudokus, and the next step is n=3n=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=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 NNN: if we ignore the column and box constraint and consider only the row constraint, then every row has N!N!N! possible combinations, and there are NNN rows, making the total number of possible combinations N!N=(n2!)n2N!^N = (n^2!)^{n^2}N!N=(n2!)n2.Note that this is a terrible upperbound: if we use this formula for n=3n=3n=3 we get ≈1050\approx 10^{50}≈1050, way above the correct answer of ≈6.6×1021\approx 6.6 \times 10^{21}≈6.6×1021Still, n=2n=2n=2 small, n=3n=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_2S1,S2 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_1S1 we get S2S_2S2however, if σ\sigmaσ swaps any digit then when we apply it to S1S_1S1 we will get a solution that does not start with 1 2 3 4, so it cannot be equal to S2S_2S2similarly, if σ\sigmaσ leaves all the digit as they were, when we apply σ\sigmaσ to S1S_1S1 the result is exactly S1S_1S1, which by assumption is not equal to S2S_2S2hence, 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 ║
╚═══╧═══╩═══╧═══╝
╔═══╤═══╦═══╤═══╗
║ 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 ║
╚═══╧═══╩═══╧═══╝
Counting puzzlesUntil 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: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)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.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)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.pythonallPuzzles = 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)A nice trick for finding minimal subsetsIf 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 SSS, we are assigning exactly SSS bits, so the binary number corresponding to the subset will be betweeen 000 and 2S−12^S-12S−1 (in our case S=N2S = N^2S=N2). So, if we iterate on every number from 000 to 2S−12^S - 12S−1 and treat each number as a binary mask, we can iterate on every subset.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 PPP which is a valid puzzle, but it is not minimal. This means that there's another puzzle QQQ which is a subset of PPP. If that's the case, wherever the bitmask of QQQ had a 1, the bitmask of PPP 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 PPP we have also already iterated on all the possible sub-subsets of PPP, 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 QQQ is a superset of PPP, the check becomes bitmask(P) & bitmask(Q) == bitmask(P), and the order of iteration must be reversed.Cool! Now do it for n=3!No.We could just run the code with n=3n=3n=3, but the code as written has a complexity of (at least? approximately?[3])O(2N2⋅N!) O(2^{N^2 \cdot N!}) O(2N2⋅N!)We are lucky that it ran in a reasonable time for n=2n=2n=2. Using the above approximation and knowing that the n=2n=2n=2 case ran in ~200 seconds, we can see that the n=3n=3n=3 should take at least 10884812810^{8848128}108848128 times the age of the universe.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[4]).ConclusionsThere 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.Open questionsNumber of possible puzzles per solutionsNot 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?An elegant way of finding the 12 solutionsAs 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.More efficient submask loopIn 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−2N-2N−2 cells, the corresponding solution is provably not unique (there must be at least two digits that do not appear in the puzzle, swapping them in the solution gives a new solution but leaves the puzzle unchanged).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[1:1] puzzles with 40 or 41 digits, meaning that to be safe the upper bound for the size of the subset should be at least N2/2N^2 / 2N2/2, if not more.Once we have decided on upperbound and lowerbound on the number of cells in the subset, we can filter for those as follows:pythonmasks = [i for i in range(2 ** (N**2)) if lowerBound <= i.bit_count() <= upperBound]
for subsetMask in masks:
# [...]ResourcesRepository with terrible python code: github.com/Fran314/how-many-4x4-sudokusPuzzles and solutions (CSV):all-solutions.csv (9 KB)distinct-solutions.csv (384 B)all-puzzles.csv (2.94 MB)distinct-puzzles.csv (125 KB)Puzzles and solutions (txt/ascii):all-solutions.ascii.txt (49.8 KB)distinct-solutions.ascii.txt (2.07 KB)all-puzzles.ascii.txt (14.7 MB)distinct-puzzles.ascii.txt (629 KB)Puzzles and solutions (txt/unicode):all-solutions.unicode.txt (109 KB)distinct-solutions.unicode.txt (4.54 KB)all-puzzles.unicode.txt (31.9 MB)distinct-puzzles.unicode.txt (1.33 MB)puzzles-with-solutions.tar.gz (tar.gz, 694 KB)https://en.wikipedia.org/wiki/Mathematics_of_Sudoku ↩︎ ↩︎excitement, not factorial ↩︎I don't think there's any way to calculate the actual computational complexity of this code without knowing a closed formula for the number of possible puzzles for a given solution, or for the number of possible solutions. I am doing some sledgehammer approximation to obtain this number: I'm counting logic inside of the subset iteration as constant, and I am assuming there are at least N!N!N! solutions (there are, clearly, many many more: N!N!N! are the ones you get from all the permutations of a single solution) ↩︎https://math.stackexchange.com/questions/856478/how-many-sudoku-puzzles-are-there-with-at-least-one-solution ↩︎HomeProjectsBlogStudiesContactsPuzzlesTIME & GILTIME & GILHomeProjectsBlogStudiesContactsPuzzles |
The analysis focuses on the enumeration and characterization of solutions for 4x4 Sudoku grids, exploring the distinction between total solutions and structurally unique puzzles. A 4x4 Sudoku is a grid of size four by four divided into four by four subgrids, requiring the digits one through four to appear exactly once in every row, column, and subgrid.
A brute force computational approach reveals that there are 288 total possible solutions for a fully filled 4x4 Sudoku. However, recognizing that the digits used are merely symbols, and any permutation of these digits results in a mathematically equivalent puzzle structure, the number of truly distinct solutions is reduced by the number of permutations of the four digits, which is 24. This yields 12 distinct solutions. This distinction is established by imposing a canonical form, such as requiring the first row to be exactly 1, 2, 3, 4, which establishes a unique correspondence between the distinct structural solutions and the total number of solutions.
Moving beyond the count of solutions, the text examines the concept of a minimal puzzle, which refers to a partially filled grid that has a unique solution, yet remains minimal in the sense that removing any of the pre-filled digits results in a grid with multiple potential solutions. The objective is to determine the number of such minimal puzzles. This requires iterating over all 288 solutions and analyzing all possible subsets of cells that could serve as the initial configuration for a puzzle.
The method for identifying minimal puzzles involves systematically checking if a subset of fixed cells corresponds to a unique solution. A key technique involves utilizing bitmasks to efficiently iterate through every possible subset of the $N^2$ cells. To ensure that the identified puzzles are truly minimal, the process must verify that no other known puzzle is a proper superset of the current one. The logic employed leverages the inherent properties of the iteration order and bitwise operations to efficiently check subset relationships, confirming that identifying subsets does not rely on checking against all potential puzzles, but rather against those already discovered, thereby ensuring the identification of the minimal set.
The computational complexity for finding these minimal puzzles is noted to be significantly lower for the 4x4 case compared to larger grids, which is a fortunate outcome given the immense theoretical complexity for $9 \times 9$ Sudoku. While the total number of possible 4x4 puzzles is derived, the distribution of these puzzles across the 12 distinct solutions is noted as non-uniform, with some solution structures yielding significantly more minimal puzzles than others. The text concludes by posing open questions regarding the structural properties that influence the multiplicity of minimal puzzles for a given solution. |