Seventeen Clues: The Smallest Sudoku That Can Exist

Seventeen. That is the smallest number of starting digits a Sudoku can carry and still have exactly one answer. Sixteen is not brutally hard, or evil, or a puzzle only a champion finishes. Sixteen is impossible, and that has been settled since 2012.

The next thing people assume is the thing this page is really about. A grid with seventeen givens looks like it must be the hardest puzzle in the world. It is not. Below is a real 17-clue Sudoku that falls apart on naked and hidden singles alone, with no pairs and no X-Wing anywhere in it, next to a 27-clue grid that stops the entire intermediate toolkit dead with 47 cells still empty. Ten extra clues, far more work.

Both grids on this page were run through a solver first. Each has exactly one answer.

Want the answer to a grid you are staring at? Sudoku Master takes a puzzle through the camera or typed in by hand and hands back the finished grid. Free, works with no signal, and the photo stays on your phone.

The floor, and what actually stands behind it

Three numbers describe the whole space of Sudoku, and they are worth having in one place.

The third row is the one that gets misquoted. What McGuire, Tugemann and Civario did was search every 16-clue arrangement and find that not one of them has a unique solution. That is a proof by exhaustion: a program, a lot of machine time, and a result that is only as good as the code and the hardware behind it. It is accepted. It is not a pencil-and-paper theorem, and calling it one gives the wrong idea about what kind of fact it is.

What it means at your kitchen table is simple enough. A grid with 16 givens is not a hard puzzle. It is not a puzzle. It has at least two answers, so there is nothing in it to deduce, and no technique in existence will pick between them. A grid with 17 can be a perfectly ordinary Sudoku with one answer reachable by pure logic.

A real 17-clue puzzle

Here it is. Seventeen digits, 64 blanks.

. . . . . . . 1 .
4 . . . . . . . .
. 2 . . . . . . .
. . . . 5 . 4 . 7
. . 8 . . . 3 . .
. . 1 . 9 . . . .
3 . . 4 . . 2 . .
. 5 . 1 . . . . .
. . . 8 . 6 . . .

Rows are numbered 1 to 9 from the top and columns 1 to 9 from the left, so r8c4 is the 1 in the bottom left region. Boxes run 1 to 9, left to right and then top to bottom.

Look at how the clues sit before you try to solve anything. Box 2, the top middle, has no clues at all. Boxes 3 and 9 have one each. Columns 8 and 9 carry one digit between them apart from the 7 at r4c9. Box 8 holds four of the seventeen, nearly a quarter of everything you are given, crammed into the bottom middle.

That distribution is the whole character of a thin grid. Cross-hatching, which asks where a digit can go inside one box, needs a box with something in it. Run it on box 2 here and you learn nothing at all.

The first digit

There is exactly one cell in this grid with a single candidate at the start, and it sits in the crowded corner. r7c5.

Row 7 already holds 3, 4 and 2. Column 5 holds 5 and 9. Box 8 holds 4, 1, 8 and 6. Put those together and the banned list reads 1, 2, 3, 4, 5, 6, 8, 9.

One digit survives. Place a 7 at r7c5.

Count the clues that did that: three in row 7, two in column 5, three more in box 8, eight of the seventeen in total. Eight clues, eight digits knocked out, one left standing. Thin grids are not short of information. The information is just piled in one corner.

The second digit, and how the grid opens

Now take row 4, which reads . . . . 5 . 4 . 7. Ask where the 1 can go in that row, rather than asking what any one cell can hold.

• r4c1, r4c2, r4c3: all three sit in box 4, and box 4 already has a 1 at r6c3. Out.
• r4c4: column 4 already has a 1 at r8c4. Out.
• r4c8: column 8 already has a 1 at r1c8. Out.
• r4c6: nothing bans it.

So the 1 in row 4 goes to r4c6. That is a hidden single, and it is the shape every move in this puzzle takes: one digit, one unit, one survivor.

The same reading works on column 7. It holds 4, 3 and 2 already. The 1 cannot go in r1c7, r2c7 or r3c7 because box 3 has the 1 at r1c8. It cannot go in r6c7 because row 6 has a 1, or r8c7 because row 8 has one. That leaves r9c7, and it is a 1.

Now the part that surprises people

Keep going in exactly that way and the puzzle finishes. All 64 blanks. Every single one of them falls to a naked single or a hidden single, and nothing else is needed anywhere in the grid.

6 9 3 7 8 4 5 1 2
4 8 7 5 1 2 9 3 6
1 2 5 9 6 3 8 7 4
9 3 2 6 5 1 4 8 7
5 6 8 2 4 7 3 9 1
7 4 1 3 9 8 6 2 5
3 1 9 4 7 5 2 6 8
8 5 6 1 2 9 7 4 3
2 7 4 8 3 6 1 5 9

No naked pair. No pointing pair. No X-Wing. The two techniques on the second rung of the ladder do the entire job on the smallest puzzle that can exist.

Every one of the seventeen is load-bearing

A puzzle is called minimal when you cannot take a single clue out of it. Take any one away and the grid stops having one answer.

At 17 clues that is guaranteed, because removing one would leave 16 and nothing with 16 givens has a single answer. What is worth seeing is how far it falls. Pull any one of the seventeen and the grid does not get harder, it stops being a puzzle: every one of those seventeen wrecks has at least six different legal completions, and rubbing out the 8 at r5c3 alone leaves more than a dozen.

Compare that with an ordinary newspaper grid. There you can often lift a clue or two and the answer stays unique, because the setter was aiming for a pleasant solve rather than a minimum.

Why sixteen cannot be made to work

There is no short proof. There is one piece of it you can check yourself at the table, and it is worth doing because it shows what kind of obstacle this is.

Suppose a puzzle's givens never use a 4 and never use a 7. Take any solution and swap every 4 with every 7. Every row still holds 1 to 9. So does every column and every box. And every given digit is exactly where it was, because none of them was a 4 or a 7. You have built a second solution out of the first.

So a proper Sudoku must show at least eight of the nine digits, whatever else is true of it. The grid above shows all nine.

That argument is airtight, it takes thirty seconds, and it gets you to eight. The floor is seventeen. Nothing that short accounts for the other nine, which is the reason the answer had to come out of a computer rather than a notebook. The two counting results at the top of this page are what make a search like that finite in the first place: strip out symmetry and the sextillions collapse to about five and a half billion grids.

Seventeen clues does not mean evil

Now the contrast. This grid has 27 clues, ten more than the one above.

. 2 . . . . 8 . .
. . . 2 . . . . 9
9 . 1 3 8 7 . . .
. . 9 . . 2 . 7 .
. 6 . . . . . . .
. 5 . . 9 4 1 . 8
. 1 2 . . 6 7 . .
. . . . . . . . 2
6 7 4 . . . . 5 .

Run naked and hidden singles on it until they stop. They place five cells and stall with 49 blanks. Add naked pairs and triples, then pointing pairs, then box-line reduction, and run the lot until nothing moves: seven cells placed altogether, 47 still empty. Everything most solvers know, applied to a 27-clue grid, gets you seven digits.

Read the last two rows of that table together. Sixty-four blanks fell to the second rung of the ladder. Fifty-four blanks beat everything up to the fifth. A clue count tells you how much of the answer you were handed, not how far apart the deductions sit, and only the second thing costs you an evening. The grading itself is worked through in what makes a Sudoku easy, medium, hard or extreme.

The word on the page is no more use than the count. Evil, diabolical, expert: a publisher chose it. An evil-labelled grid usually carries more than twenty givens, which is to say more help than the puzzle at the top of this page, and a 17-clue grid carries no label at all until somebody rates it.

What a thin grid does change

Fewer clues does change something real. It changes which move works first.

Pencil-mark the 17-clue grid above and you write 303 candidates across 64 cells, an average of 4.7 per cell. One cell holds a single candidate, the one you place first. Nine hold three, seventeen hold four, twenty-one hold five, and sixteen hold six or seven. Writing all that out before you start is an hour of work that hands you a page too crowded to read.

Four things work better on a thin grid, and they are the reason it is not the ordeal it looks like.

Go to the crowded corner first. Do not sweep the grid evenly. Find the box or the line that carries the most givens and work there, because the first placement has to come from somewhere dense. In the puzzle above, box 8 holds four clues and the first digit came out of it.

Ask about digits, not cells. The productive question in a thin grid is "where can the 1 go in this row", not "what can this cell hold". The second question has five answers nearly everywhere. The first has one answer more often than you would think.

Write candidates only where they are scarce. More than half the cells in the grid above hold five or more, and writing those out gives you a longer list to read rather than a deduction. Take a row or box that already carries givens, write that one out, use it, and clear it before you move on.

Expect a cliff, not a slope. Thin grids go slowly for the first eight or ten placements and then collapse. Once the givens stop being isolated and start sharing rows with each other, every placement creates two more.

If those first ten placements are where you always stall, cross-hatching and the two kinds of single are the pages to work through, in that order.

Where you will and will not meet one

You will not open a newspaper and find seventeen clues. The craft conventions that shaped the modern puzzle came from Nikoli in Japan, and they set at most 32 givens and symmetric clue placement. The grid above is plainly not symmetric, and it carries barely half the givens of a 32-clue puzzle.

Nor can you casually make one. Take a completed grid, rub digits out in random order, and put back any whose removal costs the puzzle its single answer. What you are left with is minimal every time. I ran that two hundred times on two hundred different completed grids, and every run stopped between 22 and 28 givens: 24 and 25 in most of them, 22 in five, and nothing below that at all. Seventeen sits five clues past the far end of that spread, which is why those puzzles are found by targeted search and not by stripping.

That is also why apps and books do not ship them. Puzzles in the low twenties are already hard enough that the extra rarity buys the solver nothing.

What a solver does with a grid this thin

I built Sudoku Master, so here is the honest boundary. Its solver is the plain backtracking kind. Type a 17-clue grid in by hand, or scan one off a page, and it either returns the finished puzzle or returns nothing. It names no techniques. It will not tell you that the grid above needs nothing above a hidden single, because it never worked that out. It just shows you the answer.

The nothing is worth knowing about. On a 17-clue grid typed in by hand, a solver that returns nothing almost always means a typo rather than an impossible puzzle. With 64 blanks there is no redundancy left to catch a slip, and one wrong digit turns a proper puzzle into a broken one.

The 4,000 puzzles the app ships run from 36 givens on easy down to 21 on extreme. None of them is a 17. That is a deliberate choice, for the reason above: below the low twenties you are collecting a curiosity, not choosing a harder puzzle.

Common mistakes

Treating seventeen as a warning. The grid on this page carries the fewest clues a Sudoku can have and asks for nothing above a hidden single.

Giving up on a thin grid before the cliff. Ten slow placements followed by a collapse is the normal shape. Ten slow placements is not a verdict.

Full pencil marks on a 17-clue puzzle. Three hundred candidates on one page is not a tool, it is a fog. Mark one unit, use it, clear it.

Cross-hatching an empty box. A box with no givens tells you nothing until its rows and columns fill in. Start where the digits already are.

Calling the 17 result a theorem someone proved on paper. It is an exhaustive computer search, it is accepted, and describing it accurately costs one extra sentence.

Hunting for a Sudoku with 16 clues. There is nothing to find. Any such grid someone shows you has at least two answers, whatever the caption says.

Questions people ask

Is an evil Sudoku the same as a 17-clue Sudoku?

No, and the two have nothing to do with each other. Evil is a grade name a publisher chose, and different sites hang it on very different puzzles. Clue counts inside any one grade vary widely. An evil-labelled grid usually has more than twenty givens, and the 17-clue puzzle above is easier than most of them.

How many Sudoku grids are there?

There are 6,670,903,752,021,072,936,960 completed grids that obey the rules, counted by Felgenhauer and Jarvis in 2005. Strip out rotations, reflections and relabelling of the digits and 5,472,730,538 genuinely different grids remain. Each one of those can be the answer to many different puzzles.

Could someone still turn up a Sudoku with 16 clues?

Only if the 2012 search was wrong. It was not a sampling exercise or a hunt that gave up early. Every 16-clue arrangement was checked, and none has a unique answer. So a 16-clue grid with one answer would have to be a bug in that program, not a puzzle nobody thought to look at.

Can I make a 17-clue puzzle myself?

Not by stripping a finished grid. Take digits out at random, keep only the removals that leave one answer, and you stop in the low-to-mid twenties nearly every time. Two hundred runs of that method landed between 22 and 28 givens, with the bulk on 24 and 25. Reaching 17 needs a targeted search, which is a computing project rather than an evening.

Is there a maximum number of clues?

Not a meaningful one. Adding a correct digit can only remove possibilities, so a grid never gains a second answer by being given more help. What it loses is interest, which is why Nikoli's convention caps a published puzzle at 32 givens. Going the other way, a grid can be almost full and still be faulty: 77 correct digits with four blanks in a rectangle can leave two legal answers.

Do all 17-clue puzzles use all nine digits?

Every proper Sudoku shows at least eight of the nine, for the swap reason above: leave two digits out entirely and they can trade places in any solution, giving you two answers. The grid on this page uses all nine.

Does a solver take longer on a puzzle with fewer clues?

A little, because a backtracking solver branches more when cells have more candidates. It does not matter in practice. A 9x9 grid is solved in milliseconds either way. The result that Sudoku is NP-complete applies to the generalised n-by-n puzzle, not to the nine-by-nine one in front of you, so it says nothing about your morning grid.

Why does a solver say my puzzle has no answer?

Almost always because a digit went in wrong, either in your typing or in a camera read. A thin grid has no slack: with 64 blanks, a single misplaced clue usually kills the puzzle outright rather than making it harder. Check the scanned or typed digits against the page before you blame the puzzle.

Keep reading

• What actually makes a Sudoku easy, medium, hard or extreme, for the grading the clue count cannot do
• Naked singles and hidden singles, with worked grids, the two moves that finished the 17-clue grid on this page
• Sudoku: the complete guide, the guide that runs from the rules to the advanced techniques
• Why some Sudoku puzzles feel impossible, for grids that stop moving with plenty of clues on the page
• The history of Sudoku, where the 32-given convention and the symmetric layout came from
• How to write a Sudoku solver: backtracking explained, for what a machine does with 64 blanks

Get it: Sudoku Master, free on iPhone and Android. Scan a printed grid or type one in, and the reading happens on your phone.