// HACKER NEWS — CYBERSECURITY
There are only twelve 4x4 sudokus (and a cool trick for finding minimal subsets)
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×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:
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.
How many 4x4 sudoku solutions exist? And of these solutions, how many are actually distinct (structurally)?