Solvers,
Every sudoku begins with its givens. This week's letter is about how few of them a puzzle can have. The full answer took years of computing to settle. Part of it you can prove yourself with a pencil.
Seventeen is the floor
A proper sudoku has exactly one solution. The givens are there to force it. Take enough of them away and a second completion appears, and the grid stops being a puzzle. So the question is easy to ask. What is the smallest number of givens that can still force a single solution?
For years the working answer was 17. Solvers collected puzzles with 17 givens, and the largest collection, kept on Gordon Royle's homepage, grew to 49,151 of them. Nobody found one with 16. That was evidence. It was not proof.
Gary McGuire, Bastian Tugemann and Gilles Civario, working from University College Dublin, set out to close the question. Their project began in August 2005. They ran an exhaustive computer search for a sudoku with 16 givens and found none. They posted the result on January 1, 2012, in a paper titled There is no 16-Clue Sudoku. The answer is 17.
No proper sudoku can start with fewer than 17 givens. That is now certain.
The 19th World Sudoku Championship opens in Kolkata on October 11. I will report on it here once the results are in.
From Claire's desk
The search needed a computer. A smaller floor needs only a pencil.
A proper sudoku must show at least eight different digits among its givens.
Here is the proof. Suppose two digits, say 3 and 7, appear nowhere among the givens. Take the solution and swap every 3 for a 7 and every 7 for a 3. Each row, column and box still holds one of every digit, so the new grid is still a valid sudoku. Every given is unchanged, because none of them was a 3 or a 7. The puzzle now has two solutions. A proper puzzle has one, so no proper puzzle can leave out two digits.
Leaving out one digit is allowed. The swap needs two absent digits to trade, and one digit alone has nothing to trade with.
Saturday's master, No. 82, printed all nine digits. The 5 appears exactly once, in row 1, column 4.
This week's editions
Seven editions ran from Monday, September 21 to Sunday, September 27. Here is each one with its count of givens.
- No. 77, Monday, easy: 48 givens
- No. 78, Tuesday, easy: 48 givens
- No. 79, Wednesday, medium: 38 givens
- No. 80, Thursday, medium: 40 givens
- No. 81, Friday, hard: 31 givens
- No. 82, Saturday, master: 24 givens
- No. 83, Sunday, expert: 28 givens
Saturday's No. 82 sat seven givens above the floor. The paper sets its master editions at 22 to 24.
Hard is the level where boards most often go unfinished. On the weekend of September 19, two solvers chose it anyway. Between that Saturday and Monday afternoon they opened nine hard practice boards and finished all nine.
In Claire's Sudoku
Practice sits on the home page, apart from the daily edition. The arrows step the level from Easy up to Master, and each board is set fresh when you ask for it.
If Friday's No. 81 felt about right, open Claire's Sudoku, step Practice to Hard, and set yourself one board this week.