Sudoku by the Numbers: 6.67 Sextillion Grids and the 17-Clue Limit

By Dawid Siedlarz · · 6 min read

Play Sudoku free →

Short answer: There are 6,670,903,752,021,072,936,960 completed Sudoku grids, about 6.67 sextillion, and 5,472,730,538 of them are truly different once you ignore relabelling, rotating and reflecting. A proper Sudoku needs at least 17 given numbers: a computer search in 2012 proved that no 16-clue puzzle has a unique solution. The game itself grew out of Latin squares, which Leonhard Euler studied in the eighteenth century.

Sudoku looks like a number puzzle, but it contains no arithmetic at all. You could replace the digits 1 to 9 with nine colours or nine letters and nothing would change. What it is really about is arrangement: putting nine symbols into a grid so that none repeats in a row, a column or a box. That kind of problem has kept mathematicians busy for over two hundred years, and Sudoku has produced some surprisingly hard questions of its own.

Before Sudoku: Euler's Latin squares

Painted portrait of Leonhard Euler in a blue robe and a soft cap, looking to the side
Leonhard Euler, painted by Jakob Emanuel Handmann in 1753. His work on Latin squares is the mathematical ancestor of Sudoku.Photo: Jakob Emanuel Handmann, public domain, via Wikimedia Commons

A Latin square is a grid filled with symbols so that each symbol appears exactly once in every row and every column. The Swiss mathematician Leonhard Euler studied them in a long paper in 1782, starting from a famous puzzle: can 36 officers, from six regiments and of six ranks, stand in a 6 × 6 square so that no row or column repeats a regiment or a rank? Euler believed it was impossible, and in 1900 the French mathematician Gaston Tarry proved him right by checking every case.

A completed Sudoku is a 9 × 9 Latin square with one extra rule: each of the nine 3 × 3 boxes must also contain every digit once. That one rule makes a huge difference. There are about 5.5 × 1027 Latin squares of size 9, but only about one in 828,000 of them is also a valid Sudoku grid.

How many Sudoku grids are there?

The exact number was calculated in 2005 by Bertram Felgenhauer and Frazer Jarvis: 6,670,903,752,021,072,936,960. Written in words, that is about 6.67 sextillion. If everyone on Earth solved one new grid every second, it would take more than 25,000 years to get through them all.

Most of those grids are copies of each other in disguise. Swap every 1 for a 2 and every 2 for a 1 and you get a "new" grid that is really the same puzzle. The same is true if you rotate or mirror the grid, swap two rows inside the same band of three, or swap two whole bands. In 2006 Ed Russell and Frazer Jarvis counted the grids that remain after removing all of these symmetries: 5,472,730,538, about five and a half billion genuinely different Sudoku solutions.

A small fact helps put this in perspective: the first row of a grid alone can be filled in 9 × 8 × 7 × … × 1 = 362,880 ways. Every one of those choices still leaves a huge number of ways to complete the grid, which is why the total is so large.

The 17-clue limit

A Sudoku puzzle on a 9 by 9 grid with thick lines around the 3 by 3 boxes and 30 given numbers
A classic Sudoku with 30 givens. Puzzles with as few as 17 givens exist; puzzles with 16 cannot have a unique answer.Photo: Lawrence Leonard Gilbert, public domain, via Wikimedia Commons

A good Sudoku has exactly one solution. The fewer numbers you are given, the harder it is to make that true, so mathematicians asked: what is the smallest number of clues a proper Sudoku can have? Puzzle collectors found tens of thousands of puzzles with 17 clues, but nobody ever found one with 16.

In 2012 Gary McGuire, Bastian Tugemann and Gilles Civario at University College Dublin settled it. Their program went through every one of the 5.47 billion essentially different grids and checked every possible set of 16 clues inside it, using millions of hours of computer time. None of them had a unique solution. So 17 is the minimum.

The idea that made the search possible is called an unavoidable set. Imagine four cells forming a rectangle across two boxes, with the digits 3 and 7 in a checkerboard pattern. If you swap the 3s and 7s in those four cells, the grid is still valid. A puzzle that gives none of those four cells can therefore be solved two ways, so at least one clue must sit inside every such set. A grid can contain many unavoidable sets, and if no 16 cells can cover all of them, no 16-clue puzzle for that grid can work.

How hard is Sudoku for a computer?

For a computer, a single 9 × 9 Sudoku is easy: a simple program that tries a number, moves on, and backs up when it hits a contradiction solves almost any puzzle in a fraction of a second. Donald Knuth's "Dancing Links" technique, published in 2000, turns Sudoku into a general problem called exact cover and solves it even faster.

The interesting part comes when you make the grid bigger. In 2003 the Japanese computer scientists Takayuki Yato and Takahiro Seta proved that Sudoku on n² × n² grids is NP-complete. In plain language: nobody knows a method that stays fast as the grid grows, and finding one would also crack thousands of other famous problems in scheduling, logistics and cryptography. Minesweeper belongs to the same family, as we explain in how to play Minesweeper.

How our Sudoku puzzles are made

Every puzzle in our Sudoku is generated fresh in your browser, in four steps:

  1. Fill a complete grid. The three boxes on the main diagonal are filled with random digits first, because they share no row or column and cannot conflict. A solver then completes the rest.
  2. Remove numbers one by one, in random order. After every removal the solver checks that the puzzle still has exactly one solution; if not, the number goes back.
  3. Stop at the target: 40 givens on Easy, 32 on Medium and 26 on Hard.
  4. Check that it can be solved by logic. A unique solution is not enough: some puzzles can only be finished with advanced techniques or trial and error. Our generator only keeps puzzles that can be solved with the methods in our Sudoku guide (naked and hidden singles, pointing and claiming, and naked pairs). On Hard, about three in ten candidate puzzles fail this test and are thrown away.

That last step is why you should never need to guess. If you get stuck, there is always a logical next move somewhere on the board. Pencil-mark notes (press N, or use the Notes switch) let you write the candidates for a cell; when you place a number, it is removed from the notes in the same row, column and box automatically.

What the numbers mean for you as a player

  1. Every puzzle you play is almost certainly new. With billions of essentially different grids and many puzzles per grid, the chance of meeting the same one twice is tiny.
  2. Fewer clues does not always mean harder. Difficulty depends on which techniques you need, not just how many numbers are given. A 26-clue puzzle can be easier than a 30-clue one.
  3. Guessing is a sign you missed something. In a well-made Sudoku, every number can be deduced. Look for a hidden single in a different unit before you guess.

Did you know?

  • The digits in every row, column and box of a finished Sudoku add up to 45, so the whole grid always adds up to 405.
  • The name Sudoku comes from a Japanese phrase meaning roughly "the digits must remain single", shortened by the publisher Nikoli in the 1980s.
  • Euler's 36-officer puzzle has no solution, but squares like it exist for every other size above 2, a result proved only in 1959.

Next: Part 3: The maths of shuffling, why every well-shuffled deck is almost certainly unique, and how many shuffles it takes.