Counting, Symmetries and Equivalence Classes of Sudoku Grids

The Great Sudoku Puzzle Hunt

Imagine you are a detective trying to count every possible way a massive, 81-room mansion could be filled with nine different types of furniture. But there's a catch: the rules are incredibly strict. In every row, every column, and every 3x3 room, you must have exactly one of each furniture type. This is the world of Sudoku, a puzzle that has captivated millions. But for mathematicians, Sudoku isn't just a game; it's a giant combinatorial maze. They want to know: just how many unique, complete mansions (or "grids") exist? And more importantly, how many of them are truly different if you ignore things like rotating the whole house or swapping the names of the furniture?

To solve this, mathematicians use a powerful tool called "group theory," which is essentially the study of symmetry. Think of symmetry like a magic mirror: if you rotate a snowflake or flip a playing card, it might look different for a split second, but it's fundamentally the same object. In the world of Sudoku, if you can turn one grid into another by swapping numbers (like turning all 1s into 2s and all 2s into 1s) or shuffling rows and columns, those two grids are considered "twins." The big question has been: if we count only the unique, non-twin grids, how many are there? For decades, the answer was found by brute-force computer power, but the steps to get there felt like a messy pile of tricks rather than a clear, logical path.

The Paper's Discovery: Finding the Hidden Pattern

In this paper, Fernanda Pereira takes a fresh look at a specific, tricky part of the Sudoku counting problem. She focuses on the "first band" of the grid—the top three rows. Previous researchers, Felgenhauer and Jarvis, had already done the heavy lifting to find that there are exactly 44 distinct types of these top-row bands. However, they arrived at this number 44 by applying a long, complicated chain of five different "reductions." It was like peeling an onion layer by layer, where each layer required a different, specific trick to remove. The result was correct, but the number 44 felt accidental, as if it were just a random stop on a long, winding road with no deep meaning.

Pereira's paper argues that 44 is not a random accident; it is a fundamental structural truth. She proposes a new, cleaner way to see the problem. Instead of peeling layers, she suggests looking at the Sudoku grid through a new lens: column partitions.

Imagine the top three rows of the grid as three separate boxes. In each box, the numbers in the three columns form a specific "team" of three numbers. For example, in the first box, the first column might hold the numbers {1, 4, 7}, the second {2, 5, 8}, and the third {3, 6, 9}. This grouping is called a "partition." Pereira's big idea is that the entire complexity of the Sudoku grid's top band can be boiled down to a simple list of these three "teams" of numbers.

She treats these three teams not as a strict order (Box 1, Box 2, Box 3), but as a multiset—a bag where the order doesn't matter, but duplicates do. If you have three identical bags of numbers, that's one thing; if you have two identical and one different, that's another. The paper proves that two Sudoku bands are "twins" (equivalent) if and only if their bags of number-teams are the same, even if you shuffle the numbers around (relabeling) or swap the bags.

The "Hand-Calculated" Breakthrough

The most exciting part of the paper is how she counts these bags. Instead of relying on a supercomputer to check millions of possibilities for the final result, Pereira uses a mathematical theorem called Burnside's Lemma. This theorem is like a clever counting shortcut that lets you figure out how many unique groups exist by looking at how many things stay the same when you apply different symmetries.

By applying this theorem to her "bag of partitions" idea, she is able to derive the number 44 through a closed, analytical formula. She breaks the problem down into 30 different types of number-shuffling patterns (called cycle types). For each pattern, she calculates how many "bags" remain unchanged. She then adds up the results of 19 specific non-zero calculations. The final sum, divided by a specific number, lands exactly on 44.

However, the path to this elegant formula did involve some computational assistance. While the final derivation of the 44 classes is a closed-form calculation that requires no computer enumeration, the paper notes that the author used AI tools to assist in developing the mathematical arguments and wrote Python scripts to perform computational verifications. These scripts independently checked the decomposition of the counts and the final sum against direct evaluations over all possible permutations. This ensures the "hand-calculated" logic holds up against brute-force reality, confirming that the 44 classes are indeed the correct structural result.

This is a major shift in perspective. The paper explicitly argues against the idea that 44 is just a messy byproduct of a long, ad-hoc reduction process. Instead, it shows that 44 is the natural result of counting the unique ways to arrange these number-partitions under the rules of symmetry.

The Bigger Picture

While the main focus is on the 44 classes of the top band, the paper also touches on the total count of all unique Sudoku grids. It confirms the previously known number of 5,472,730,538 essentially different grids (a number found by Russell and Jarvis using computers). Pereira's method doesn't just re-verify this; it provides a structural explanation for the 44 classes that make up the foundation of that larger count.

In short, the paper takes a number that looked like a random stop on a long journey and reveals it as a destination with a clear, beautiful map. It replaces a chain of five complicated tricks with a single, elegant invariant (the multiset of partitions) and a single, powerful calculation. The result is a proof that the 44 classes are not an accident of computation, but a fundamental feature of the Sudoku universe, with the final analytical steps achievable by hand and the underlying logic rigorously verified by computer.