GoKawiilThere are only twelve 4x4 sudokus - and a cool trick for finding minimal subsets
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 × N N \times N N×N sudokus where N = n 2 N = n^2 N=n2 for some integer n n n. For n = 2 n=2 n=2 we get 4x4 sudokus, and the next step is n = 3 n=3 n=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 ║ ╚═══╧═══╩═══╧═══╝
... continue reading