The history of Sudoku

Sudoku feels Japanese, and its name is. But the puzzle itself was born in the United States, grew up in Japan, and only became a worldwide habit after a retired judge from New Zealand taught a computer to write it.

Latin squares

The mathematical idea underneath Sudoku is old. A Latin square is a grid in which every symbol appears once in each row and once in each column. The Swiss mathematician Leonhard Euler wrote about them in the 18th century, and they've been used since in everything from experimental design in agriculture to error-correcting codes. A finished Sudoku is a Latin square with one extra condition: the nine boxes must also contain every digit.

A false start in Paris

In the 1890s, French newspapers ran number-placement puzzles that come remarkably close. Around 1895, the daily La France printed 9×9 grids to be filled with 1 to 9 so that rows, columns and diagonals each held every digit — and the 3×3 squares happened to as well, though they weren't marked out. The puzzles faded away around the First World War, and nobody seems to have picked up the thread.

Number Place

The puzzle we know first appeared in 1979, in American puzzle magazines published by Dell, under the name Number Place. It's usually credited to Howard Garns, a retired architect from Indiana who built puzzles in his spare time. He died in 1989, before his invention became famous, and he's thought never to have known how far it went.

"The digits must be single"

In 1984, the Japanese puzzle publisher Nikoli came across Number Place and brought it to Japan under a long, playful name that translates roughly as "the digits must be single" — single in the sense of unmarried. It was soon shortened to Sudoku: su for number, doku for single.

Nikoli changed the puzzle in ways that still define good Sudoku. Its editors limited how many givens a puzzle could show and arranged them in symmetrical patterns, and, most importantly, they made the puzzles by hand and cared about the solving experience: a good puzzle leads you along a path of logic rather than leaving you to grind through possibilities. In Japan the puzzle grew steadily through the 1980s and 1990s, though it remained mostly unknown in the West.

The 2005 craze

Wayne Gould, a New Zealander who had served as a judge in Hong Kong, found a Sudoku book in a Tokyo shop in 1997. He spent the next six years writing a computer program to produce puzzles in quantity, then offered them to newspapers. The Times in London published its first on 12 November 2004. Other British papers followed within weeks, and by the middle of 2005 it was everywhere: on trains, in offices, on the front pages of newspapers that advertised their puzzles to win readers.

The craze reached America and the rest of Europe that same year. A British TV channel even carved a giant Sudoku into a hillside. In 2006 the first World Sudoku Championship was held in Lucca, Italy, and was won by Jana Tylová of the Czech Republic. The championship has run every year since.

A few numbers

• There are 6,670,903,752,021,072,936,960 different completed Sudoku grids, as Bertram Felgenhauer and Frazer Jarvis calculated in 2005. If you treat grids that are just rotations, reflections or relabellings of each other as the same, the count drops to about 5.5 billion.
• The fewest givens a Sudoku can have and still have one solution is 17. That was settled in 2012, when Gary McGuire and colleagues at University College Dublin ran an exhaustive computer search showing that no 16-given puzzle works.
• Solving Sudoku on ever larger grids is, in the technical sense, NP-complete — one of the family of problems for which no fast general method is known. For a 9×9 grid that doesn't matter: a computer solves one in a fraction of a millisecond.

Variants

Once a puzzle catches on, people start bending it. Some popular variants:

• Killer Sudoku adds dotted cages, each with the sum of its digits. Often there are no givens at all.
• Diagonal Sudoku asks for 1 to 9 along both long diagonals too.
• Jigsaw Sudoku replaces the square boxes with irregular shapes.
• Mini and giant grids: 6×6 with 2×3 boxes for beginners, 16×16 with hexadecimal digits for the patient.

Calcudoku is a close cousin: a Latin square without the boxes, where cages show a target and an operation.