Why Some Sudoku Puzzles Feel Impossible

A Sudoku that feels impossible almost never is. Four things produce the feeling and all four look identical from where you are sitting, which is the whole difficulty. Your technique has run out one rung below what the grid needs. Or a digit you wrote twenty minutes ago is not the one in the answer, and it has been quietly deleting that answer ever since. Or your eyes have stopped reading the board. Or, rarest by a long way, the puzzle is faulty.

Telling them apart takes about two minutes, and this page does it on one real grid: a 26-clue puzzle that stops dead with 26 cells still empty, and the single move that finishes it.

All four diagnoses rest on one fact. A properly made puzzle has exactly one solution, so nothing left in it is out of reach and no guess is ever needed. A grid that will not move is reporting on your technique, your last hour or the printing. It is not reporting that the puzzle cannot be done.

Solving on a screen instead? Sudoku Master ships every puzzle with its own solution, so a wrong digit is counted as it lands rather than surfacing nineteen moves later. Free, and it works with no signal.

The four, and the test for each

Run them in that order. The first is far and away the most common, and the last is far and away the rarest, which is the opposite of the order most people reach for.

The wall: the moment scanning stops paying

Here is the puzzle. Twenty-six givens, one solution, and a hard grade on the set it came from.

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

Cross-hatching and singles go through it well. Sweep each digit box by box, rule out every line that already holds a copy, take whatever survives, and 29 digits go in without a fight. Then the grid looks like this and does not move again.

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

Cell names read r8c1 for row 8, column 1, with rows counted from the top and columns from the left. Boxes count 1 to 9 the same way, box 1 top left and box 9 bottom right.

This is the shape of an impossible-feeling grid, and it is worth looking at properly. Three rows are complete, and so are columns 4 and 5. Twenty-six cells are blank. Sweep all nine digits again and not one of them has a single home anywhere: every box missing a digit has at least two places to put it, and box 9 can still take its 9 in seven of them. Nothing is wrong, nothing is close, and nothing gives.

That is the wall. It has a precise meaning: the puzzle has stopped answering the only question you have been asking. Scanning asks "where can this digit go in this box", and the grid has arranged itself so that the answer is always "more than one place". Ask a different question and the wall is one cell deep.

The different question, on row 8

Row 8 reads like this, with five blanks:

. 1 7 6 8 . . . .

Write out what each blank can still hold. The digits missing from the row are 2, 3, 4, 5 and 9.

Look at r8c6 and r8c8. Both hold exactly 3 and 9. You do not know which gets which, and you do not need to. Between those two cells the 3 and the 9 are spoken for, so no other cell in row 8 can take either digit.

Cross the 3 and the 9 out of r8c1. It read {2,3,9}. It now reads 2.

Place a 2 at r8c1 and the puzzle falls over. Every one of the remaining 25 cells goes in on naked and hidden singles, with no further technique of any kind. One deduction, twenty-six cells.

That is the thing worth taking away. Hard puzzles are not hard because they demand twelve clever moves. They are hard because they demand one, and until you know that one, there is nothing at all.

The same wall wears four other names

This grid is generous. It offers the same rescue by several routes, and it is useful to see that they are the same rescue.

Follow the 6. In box 9 the only cells that can hold a 6 are r7c9 and r9c9, and both sit in column 9. So column 9 gets its 6 from box 9, which strikes the 6 out of r5c9 and r6c9. That is a pointing pair, and it also finishes the puzzle.

Now come at the same digit from the column. In column 8 the only cells that can hold a 6 are r5c8 and r6c8, and both sit in box 6. So box 6 gets its 6 from column 8, which strikes the 6 out of r5c9 and r6c9 again. That is box-line reduction, and it lands on the same two candidates.

There are also two textbook X-Wings on the 6 in this grid. Both of them eliminate exactly the same two candidates as the pointing pair, for considerably more work. Reaching for the fanciest technique on the board is a common response to feeling stuck, and here it buys nothing at all. The cheapest move available was a pair in a row.

When the grid stopped having an answer twenty minutes ago

The second cause is worse than the first, because it feels like progress right up until it does not.

Go back to the stalled grid. r8c9 shows {2,4,5,9}. All four are real candidates; not one of them breaks a row, a column or a box. The truth is 5. Write 2 instead.

Now count what that lie buys you. Eighteen further digits go in on naked and hidden singles, cleanly, with no contradiction: r8c7, then r3c7, r3c9, r7c7, r8c8, r7c9, r5c9, r7c2, r3c2, r3c3, r6c3, r5c1, r5c6, r5c8, r6c6, r6c8, r7c1 and r8c1. Five boxes. Nineteen cells filled. Every one of them forced, and every one of them wrong.

The grid dies at r8c6, which runs out of candidates with seven cells still blank. By then the digit that caused it is nineteen placements back and looks exactly as reasonable as the eighteen that followed it.

So the check comes before the effort rather than after it. Read the nine rows, the nine columns and the nine boxes for a digit that appears twice. That alone finds most errors, and the two quieter legality tests are step 1 of the checklist for a stalled grid.

Then the harder half. Where is it? Start at the cell that died and work back, asking of each digit which unit forced it. The first one you cannot answer for is the lie, or its neighbour. Expect to go back further than feels reasonable. The cascade above ran through five boxes before anything complained, and if that search comes up empty, starting again from the givens is quicker than it sounds.

Stale pencil marks do the same damage by a slower route. A candidate you crossed off in your head and never crossed off on the paper is a wrong digit you have not written down yet.

When it is your attention and not the grid

The third cause has a tell you already know: the puzzle you could not touch last night falls apart in four minutes over breakfast. Nothing changed on the page.

Your eye files a region as checked and then stops reading it, which is why the cell you cannot see is one you have looked straight at several times. Three things help, and all of them are cheap.

Sweep by digit, not by cell. Take the 1 through the whole grid, then the 2. Reading cell by cell means asking nine questions per cell and answering them badly. Reading digit by digit means asking one question nine times.

Turn the page round. Rotating the grid, or holding it up to the light from the other side, breaks the shape your eye has memorised. It sounds like superstition. It works often enough to be worth the four seconds.

Stop. Ten minutes away returns more than another ten minutes of staring ever will, and the puzzle does not expire.

When the puzzle really is broken

This is rare, and it is worth naming precisely because people reach for it far too early. Two different faults hide under it.

A misprint. A digit was set wrong on the page. This one usually announces itself, because the grid turns illegal somewhere and a minute of checking for a repeated digit finds it.

Two solutions. This one is quieter and much stranger. The puzzle stays legal all the way to the end, and then hands you a choice with nothing to choose on. A puzzle like that is not difficult. It is faulty, and no technique in existence will finish it, because there is nothing left to deduce.

Here is the smallest version of the fault, built from the same puzzle's solution with four cells removed.

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

Seventy-seven of the 81 cells are filled and the puzzle has two answers. The four blanks are r2c8, r2c9, r6c8 and r6c9, a rectangle sitting in two rows, two columns and two boxes. Rows 2 and 6 each need a 3 and a 7. Columns 8 and 9 each need a 3 and a 7. Put 7 and 3 in row 2 and the rest follows; put 3 and 7 in row 2 and the rest follows just as well. Both grids obey every rule in the game.

That pattern is why generators check uniqueness before publishing, and why faulty puzzles are much rarer than the internet suggests. If you think you have one, the honest test is to finish it twice, starting from opposite corners, and see whether you arrive at the same grid. Suspect yourself first. Suspect the puzzle fourth.

Why the word on the label means nothing

Some of the impossible feeling is manufactured, and not by the puzzle.

No two publishers share a difficulty scale. One paper's hard is another paper's medium, and neither of them is lying. There is no standards body and no shared grading engine, so a reader who finds the LA Times hard puzzle brutal and the same day's paper elsewhere gentle has learned nothing about either puzzle. Grade names are also marketing. "Evil", "diabolical" and "impossible" are labels a publisher chose, and any of them may sit on a grid that falls to a single pointing pair.

Clue count is not difficulty. This is the most common mistake in Sudoku writing and it makes people despair at the wrong grids. Take the puzzle sets in the app I built: hard runs 26 to 28 givens, extreme runs 21 to 27, and the ranges overlap. The same 26-clue grid can be filed under either name, because what sets difficulty is the hardest technique the grid forces you to use, and how many times it forces you.

Few clues does not mean unfinishable. Seventeen is the proven floor: in 2012, McGuire, Tugemann and Civario searched every arrangement of 16 clues by computer and found that not one of them has a unique solution. So a grid with 16 givens can never be a proper puzzle, while 17-clue puzzles exist and still have exactly one answer reachable by pure logic. Twenty givens is not a verdict.

The grid on this page is a fair example of all three. Twenty-six clues, filed as hard, and the whole thing turns on one pair in row 8.

What I built, and what it will not do for you

I built Sudoku Master, and it is a decent referee and a poor teacher. Give the solver a printed grid and it returns the finished puzzle or it returns nothing, and nothing is the useful reply: the digits as they stand no longer fit together. It will not name the technique you are short of, because there is no technique-by-technique commentary in it. Know that before you reach for it at the exact moment you are stuck.

The part that bears on the second cause above is duller than any hint. Every puzzle the app deals carries its own answer, so a wrong digit is counted as it lands rather than nineteen placements later. Nothing about that is clever. It is the difference between losing a minute and losing an evening.

Common mistakes

Deciding the puzzle is broken. It is the rarest cause and the first one people name. Work the other three first.

Hunting the hardest technique you know. The grid above holds two real X-Wings that do exactly what a pointing pair does. Start at the bottom of the ladder every time.

Re-scanning for the fifth time. If two full digit sweeps have produced nothing, the grid is not withholding a hidden single. It is asking a different question, and more scanning cannot answer it.

Carrying on after a doubt. A digit you placed on a hunch is worth going back for at once. Nineteen forced placements is what one of them cost on this page.

Reading the difficulty label as a fact. It is a publisher's word for a grid, not a measurement, and it does not transfer between papers or apps.

Counting clues to decide it is unfair. A 30-given puzzle built around a box-line reduction is harder than a 22-given one that falls to singles.

Questions people ask

How do I tell a mistake from a technique I have not learned?

Check legality first, because it costs a minute and the alternative costs an evening. If the grid is legal, it is almost certainly fine and the move exists, so the thing to change is the question you are asking it: stop sweeping digits through boxes and write out the candidates for one tight unit instead. If the grid is not legal, stop solving and go and find the digit.

Do newspapers ever print a Sudoku wrong?

It happens, and far less often than it gets blamed. Put it fourth on the list of suspects rather than first. A misprint normally leaves the grid illegal, which is the one fault a one-minute check hands you outright, so you rarely have to argue with yourself about it.

Is a puzzle with fewer clues harder?

Not reliably. Difficulty is set by the hardest technique the grid forces on you, not by how many digits it starts with. Puzzle sets routinely overlap on clue count across two different grade names. A 21-clue grid that falls to singles is easier than a 28-clue one that needs an X-Wing.

Is the hard puzzle in one newspaper the same as hard in another?

No, and there is no scale that would make it so. Publishers grade with their own generators and their own labels, so an LA Times hard, a Times hard and an app's hard are three unrelated statements. Compare a paper against itself over a week instead.

My app says the puzzle I typed in has no solution. What now?

Check what went in before you blame the puzzle. One mistyped given, or one 6 that a camera read as an 8, turns a sound puzzle into one nobody can finish, and every answer you ask for afterwards will be wrong. Compare the givens against the page digit by digit, then try again. If it still comes back empty, the fault is on the page. Scanning a Sudoku with your phone covers the ways a grid gets mangled on the way in.

Can a Sudoku have more than one answer?

A properly made one cannot. A faulty one can, and the usual shape is four cells in two rows, two columns and two boxes holding the same two digits, as in the grid above. Generators test for this before publishing, so it is rare in print and more common in puzzles typed in by hand.

Is it cheating to check the answer?

That is your call, not a rule. The useful distinction is what you ask for. A full solution ends the puzzle. Asking only whether the grid is still legal tells you which of the four causes you are dealing with and leaves every deduction still standing.

Keep reading

• The complete Sudoku guide, the overview, with every technique in the order you meet them
• What actually makes a Sudoku easy, medium, hard or extreme, for why the label on the page is not a measurement
• Naked pairs, triples and quads, the technique that broke the grid above in one move
• Pointing pairs and box-line reduction, the rung most self-taught solvers are missing
• Seventeen clues: the smallest Sudoku that can exist, for why a thin-looking grid is not a verdict
• Newspaper Sudoku: USA Today, LA Times and the Washington Post, for how the dailies actually compare

Get it: Sudoku Master, free on iPhone and Android. Four graded sets, 4,000 puzzles bundled into the app, and no ads while you solve.