Sudoku Puzzle Generator

Two sudoku grids sit side by side. One has 26 numbers printed in it, the other 28. Most people would call the first the harder puzzle, because it gives less away. It is not. The grid with 28 clues cannot be finished without a three-cell argument that many solvers never learn, while the barer one yields to patient elimination. The number of clues tells you how much ink was saved. It does not tell you how hard you will have to think.

That gap, between how a puzzle looks and what it demands, is the most useful thing to understand about sudoku. Everything else, including its odd history, follows from one short rule.

One rule and nine symbols

The rule, as the Japanese publisher Nikoli states it: place a number from 1 to 9 in each empty cell, so that each row, each column and each 3 by 3 block contains all the numbers from 1 to 9. The point that surprises newcomers is that no arithmetic is involved at all. The digits are only nine different marks, and the puzzle would be the same if other symbols were used. Mathematicians treat the puzzle as a problem of coloring a graph: the Sudoku graph, as Wikipedia describes it, has 81 vertices, one for each cell, joined wherever two cells share a row, a column or a block.

The cells printed at the start are the givens, or clues. The solver’s whole job is to extend them, one certain step at a time.

How many finished grids are there to aim for? Bertram Felgenhauer and Frazer Jarvis counted them by computer: 6,670,903,752,021,072,936,960. Many of those are the same grid in disguise, turned around or with the digits renamed, and when Ed Russell and Jarvis removed the disguises 5,472,730,538 essentially different grids remained. Either number is far too large for a publisher ever to run out. It also explains why a generator can begin from a fresh random grid every time. A filled grid costs a computer almost nothing, and the craft lies entirely in deciding which numbers to rub out.

From Number Place to a registered name

The puzzle is American and its name is Japanese. Its first known appearance is in a 1979 issue of Dell Pencil Puzzles and Word Games, under the title Number Place. Dell printed no byline. The person credited is Howard Garns, a retired architect from Indiana, and the credit rests on a piece of detective work. Will Shortz, the crossword editor of The New York Times, found that Garns’s name stood in the magazine’s list of contributors whenever Number Place appeared and was missing whenever it did not. Garns died in October 1989, long before the puzzle became an international craze.

Nikoli found Number Place in an American puzzle magazine and introduced it to Japanese readers in 1984. Its first title there was a whole sentence, Suuji wa dokushin ni kagiru, which the company translates as the number is limited to only a single, unmarried one. That was too long, so it was cut down to Sudoku: su for number, doku for single. Nikoli is candid that the puzzle is not its own invention. What it added came in 1986, a house rule that the clues must be arranged in a symmetrical pattern, and after that, by its own account, the puzzle became a big hit.

The name is a registered trademark of Nikoli in Japan. Other Japanese publishers, the company notes, call the same puzzle Number Place.

The trip back west took one person. Wayne Gould, a New Zealander who had been a judge in Hong Kong, saw a book of the puzzles in a Tokyo bookshop in 1997 and spent the next six years writing a program that makes them. He placed one in a New Hampshire paper, the Conway Daily Sun, in September 2004, then persuaded The Times in London, which printed its first on November 12 of that year. Within months the puzzle had gone from obscurity to the front pages of British national newspapers, and other papers took it up as a regular feature.

Why there must be exactly one answer

A proper sudoku has one solution and only one. McGuire, Tugemann and Civario put it flatly in their paper on the subject: it is always understood that a valid puzzle must have only one completion. This is not a nicety. If two different grids both fit the clues, then at some cell nothing printed on the page can tell you which digit is right, and logic stops. Wikipedia’s glossary of the puzzle records the same convention: a sudoku is always expected to be proper unless the setter says otherwise.

One consequence is easy to check by eye. A puzzle whose clues use only seven of the nine digits can never be proper, because the two missing digits could be exchanged everywhere in any solution to give a second one. At least eight different digits must appear among the givens. The condition is necessary and nowhere near sufficient, which is why a generator has to test every candidate puzzle by searching for a second solution.

That search is cheap for a machine. Peter Norvig’s essay on the subject sets out to solve every puzzle with two ideas, constraint propagation and search, where the search always tries the square with the fewest remaining possibilities first. A program built that way can be asked a sharper question than a person ever asks. Not what the answer is, but whether a second one exists.

From singles to fish

People do not search. They look for a step that is certain, take it, and look again. The steps have names, and the names form a ladder.

The bottom rungs are the singles. A naked single is a cell where every digit but one already appears in its row, column or box, so only one can go there. A hidden single runs the other way: within some row, column or box, a digit has just one cell left that can take it. Tom Davis, in a handout written for math circles, files both under obvious strategies and gives them the names used here. Many puzzles need nothing else from start to finish, and those are the ones that deserve the word easy. Harder ones end the same way: once the difficult step is found, the remaining cells fall to singles one after another.

Above them come the locked candidates, as Davis calls them. If, inside one box, a digit can only go in cells that lie along a single row, then it must be in that row within that box, and it leaves the rest of the row: a pointing pair or triple. The mirror image, where a row’s only places for a digit sit inside one box, clears the rest of the box.

Then come the subsets. Two cells in a unit that hold the same two candidates and nothing else form a naked pair, and those two digits leave every other cell of the unit. A hidden pair is two digits confined to two cells, which evicts everything else from those cells.

Triples and quads extend the idea to three and four cells, with a twist Davis points out: the three digits only have to be the sole candidates of the three cells taken together, and no single cell has to hold all three. Cells holding 1 and 3, 3 and 7, and 1 and 7 make a naked triple. The reason is a count: put one of those digits anywhere else in the unit and the three cells are left with two digits between them.

Quads are rare. In 4,000 hard and expert puzzles generated for this page, 235,079 steps in all, the solver needed a naked quad five times and a hidden quad never. The closing run of singles in those same puzzles was never shorter than 11 cells, and in half of them it was 34 or longer.

The top rungs used here are two fish and a wing. An X-wing takes one digit and two rows in which it has exactly two possible cells, in the same two columns. The digit must occupy opposite corners of that rectangle, so it can be removed from the rest of both columns. A swordfish does the same with three rows and three columns. The XY-wing uses three cells with two candidates each: a hinge AB that sees a cell AC and a cell BC. Whichever way the hinge falls, one of the other two becomes C, so any cell that sees both of them cannot be C.

What the clue count hides

Now return to the two grids. Both come from the generator on this page with seed 2026 and half-turn symmetry. Asked for Hard, it produces a puzzle with 26 clues on its 27th attempt. Solved by always taking the simplest available step, it needs 57 steps: 43 naked singles, 12 hidden singles, one pointing move and one hidden pair. Weighting those at 1, 2, 5 and 10 points gives a score of 82. Asked for Expert with the same seed, it produces 28 clues, two more, and a path that includes a naked triple and an XY-wing for a score of 137. The Easy puzzle from that seed has 36 clues and scores 45.

So difficulty is a property of the path. The honest way to grade a puzzle is to solve it the way a person would and record the hardest step that could not be avoided. Clue counts are a poor proxy: McGuire and his colleagues observe that newspapers and magazines usually give around 25 clues, and the three puzzles above show how little such a number settles. The score is this page’s own arithmetic and should not be compared with ratings printed anywhere else.

How bare can a proper puzzle be? For several years the conjectured answer was 17, since thousands of puzzles with that many clues were known and none with 16. McGuire, Tugemann and Civario closed it with an exhaustive computer search. The computation ran from January to December 2011 and took about 7.1 million core hours on a cluster at the Irish Centre for High-End Computing. It found no 16-clue puzzle, so 17 clues is the minimum. The generator here does not try to reach it. Its minimal puzzles, from which no single clue can be removed, average about 24.

A ladder of thirteen named techniques does not reach every puzzle, and a grader should say so. In a test of 5,000 fully dug grids made for this page, 1,312 could not be finished with them. Such puzzles need longer chains of reasoning or, as Wikipedia’s glossary allows for the most difficult examples, a guess followed by backtracking. This page labels them as beyond its techniques, never calls them expert and never generates them. The solver is also a rough model of a person: it takes naked singles before hidden ones, though many people spot hidden singles first.

On paper the same ladder applies, and two habits help. Write small candidate digits in a cell only when plain scanning has stopped paying, because notes are for the stage after the simple placements run out. Erase a candidate the moment a placement kills it, since every technique above the singles depends on the notes being true. Print fewer puzzles to a page than you think you need. Pencil marks want room.

Then pick the level by what you want to practice, not by how empty the grid looks. A sparse puzzle may be an afternoon of singles. A fuller one may be hiding a fish.