Addictive, seductive, sudoku


Sudoku is nothing short of a global phenomenon, a once-in-a-generation craze that has, within a year, caused millions of us to overshoot railway stops, sneak away from family gatherings and forgo conjugal relations, all in the hope of filling in just one more square.

Addictive, seductive, sudoku
• 24 December 2005
• From New Scientist Print Edition. Subscribe and get 4 free issues.
• Ivan Semeniuk


Enlarge image
Tangrams

Enlarge image
Doublet

Enlarge image
Sudoku
IN BOSTON, a Japanese restaurant hands out $10 gift certificates to patrons who can finish one before they finish their sushi. In the west of England, motorists passing a hillside near Bristol marvel at a giant one that appeared overnight. In Paris and New York, enthusiasts flock to tournaments where they can do them by the dozen. All over the world, newspapers have learned that unless they run at least one every day, they can expect to see their circulation plummet. And in bookstores everywhere, the accumulated works of human civilisation have been shoved aside to make way for yet another shipment of sudoku books.
"I've had people say that they've tried it after hearing me talk about it on the air," says John Williams, a Chicago radio host and sudoku fiend. "And then they tell me they're addicted." In the past, Williams says, he never paid much attention to puzzles. Now he does sudokus in weekly batches, provided by a local newspaper that publishes his completion times as a challenge to readers.
Williams is not alone. Sudoku is nothing short of a global phenomenon, a once-in-a-generation craze that has, within a year, caused millions of us to overshoot railway stops, sneak away from family gatherings and forgo conjugal relations, all in the hope of filling in just one more square. So how is it that this apparently simple number grid has become the puzzle equivalent of a worldwide pandemic?
The sudoku craze began - as pandemics often do - with just the right combination of social upheaval and international travel. The upheaval was Hong Kong's return to Chinese rule in 1997. Among the millions affected was New Zealander Wayne Gould, a judge in the Hong Kong court system who was on the lookout for a project for his retirement, which would begin as the colonial administration came to an end.
Gould makes no claims to any great mathematical or computer wizardry, but he has a knack for numbers. So he decided to idle away his golden years fiddling with computers. "I wanted to perfect my hobby of programming," he says. "It just so happened that the first project that came along was the sudoku puzzle."
Just before retiring, Gould had picked up a book of puzzles during a trip to Tokyo. It was his first encounter with sudoku - which translates roughly as "single numbers" - a handmade puzzle popular in Japan since the mid-1980s. Sudoku was introduced there by the Nikoli company, a publisher that specialises in logic puzzles, which in turn got the idea from a US puzzle magazine published by Dell Magazines (no relation to Dell computers) in 1979. The puzzle was originally created for Dell by Howard Garnes, an architect from Indianapolis who died in 1989.
Gould knew none of this. All he knew was that he was quickly running out of sudokus and he wanted more. So he decided to write a computer program to generate new puzzles. Little did he know that he was embarking on a six-year odyssey that would lead him deeper into the number-crunching wilderness than he could ever have expected, and then launch a global obsession.
Getting a computer to generate a sudoku is relatively easy. One way is to start with a complete puzzle grid and randomly delete numbers until one more deletion would mean the puzzle no longer had a unique solution. What preoccupied Gould for six years was generating puzzles that were as subtle and enjoyable as the human-made ones in his book, and with a full range of difficulty. That means the software has to take into account the number, variety and complexity of the logical steps needed to solve a particular sudoku. "Grading the puzzle is one of the most difficult things about writing a sudoku program," Gould says. "There are about 15 or 20 factors that go into grading."
In November 2004, Gould's sudoku puzzles began appearing in the UK in The Times newspaper. Gould was not prepared for what happened next. "I knew the puzzle would reach a lot of people and I always expected it would be popular," he says. "Somehow I hadn't done the math that 'popular' times 'a lot of people' equals a craze."
Puzzle crazes are a recurring theme in history. "Every now and then - usually every 50 years or so - a puzzle comes along that just catches on like wildfire," says Marcel Danesi, professor of semiotics and communication theory at the University of Toronto, Canada, and author of The Puzzle Instinct. Historical examples include the shape puzzle called tangrams and the word game known as doublet, invented by Lewis Carroll (see Diagram). In 1878, American puzzle expert Sam Loyd unleashed the "14/15 puzzle", which consisted of 15 sliding tiles in a 4-by-4 tray. In Loyd's own words, the puzzle "drove the entire world crazy" - which is understandable, since he designed it so that it could not be solved. More recently, Hungarian inventor Ernö Rubik's eponymous cube generated the sort of global mania that is difficult to understand if you haven't lived through it. Sudoku is in the same league.
In fact, sudoku possesses a number of qualities that suggest it will become one of the biggest puzzle crazes ever, if not the biggest. "This is a good puzzle," says Danesi. "It is apparently simple, but it challenges you, and then you're hooked."
And that's not all. One of sudoku's key advantages is that it uses numbers rather than letters or words, so it crosses international boundaries effortlessly. Sudoku is so universal that it is plausible that alien civilisations have been doing them for aeons. It is a pure logic puzzle that requires nothing more than working intelligence to solve. The rules are simple enough for anyone to start right away, and the puzzle can be pitched at the right level of difficulty to satisfy virtually any player
"That's what I love about sudoku," says Williams. "You don't have to be an expert at anything to do it. You know the answer is there, staring back at you, and by concentration alone you can muscle it out."
As an added attraction sudokus feature a particular kind of mathematical beauty. They are a special form of Latin square, first described in 1783 by the Swiss mathematician Leonhard Euler. A Latin square is any square grid of symbols in which no symbol is repeated in any row or column. Sudokus have the extra constraint that the grid is divided into smaller squares, each of which also contains a full set of numbers.
In a standard sudoku, the grid is a 9-by-9 square subdivided into nine 3-by-3 squares. Only two smaller grids share this property: the first is a single square, which is trivial; the second is a 4-by-4 grid, which can be turned into a simple, beginner-level sudoku. But by general consensus the fun doesn't start until you play the 9-by-9 grid. And that's where the fun ends, too. Gould has generated 16-by-16 grids, but the results are not nearly as satisfying. "It's not worth the effort," he says. "It's a whole lot more work with no more buzz than you get from the 9-by-9. It just becomes a job."
And that's the key. For some reason sudoku gives you a buzz. Kevin Grobman, a developmental psychologist at Louisiana State University in Baton Rouge, thinks that is because it clicks with a basic element of our psychological make-up. "Starting during infancy, we direct our attention to things that are moderately more complex than what we already understand," he says. And when we succeed at challenging tasks, we feel more competent. "With more challenging sudoku puzzles available, we can continue through a cycle of enhancing our sense of personal competence and becoming more motivated to solve new problems."
This observation points to another aspect of sudokus that helps make them a craze. It's not just one puzzle; it's a lifetime's supply. Earlier this year, Frazer Jarvis of the University of Sheffield, UK, and Bertram Felgenhauer of the Dresden University of Technology in Germany enumerated all possible 9-by-9 sudoku grids. Their result was a staggering 6,670,903,752,021,072,936,960, or approximately 6.67 billion trillion grids. This vast number is, however, only a fraction of the total number of sudoku puzzles, since each completed grid is simply the end point for a vast array of possible starting configurations.
It's easy to understand why a puzzle that can be adjusted to offer constant stimulation would do better than others. Less clear is why such an abstract pursuit should turn our cranks in the first place. Evolutionary psychologists have observed that such tasks offer good practice for spatial and mechanical reasoning. But the celebrated English amateur puzzlist and mathematician Henry Dudeney probably captured it best when he wrote: "A good puzzle, like virtue, is its own reward."
This should come as welcome news to all us virtuous addicts doing sudoku puzzles by the bathroom light at 3 am. Not that Wayne Gould is getting much sleep either. Ever since he touched off the sudoku craze he's been getting about a thousand emails a day and is in constant demand to preside over all manner of sudoku-related events. "It's been hectic," he says. "I haven't had much time to rest at all...In fact I'd like to get my retirement back."
From issue 2531 of New Scientist magazine, 24 December 2005, page 45
How do you do yours?
If you don't yet know how to do a sudoku then let us be the first to say: welcome back to civilisation, how did the solo trek across Antarctica go? For the record, a completed puzzle consists of an 81-square grid in which every row and column contains the digits 1 to 9 with no repeats. The grid is also subdivided into nine smaller squares of nine squares each, in which the same rule applies. That's it. The elegance of the puzzle lies in using these rules as logical levers to uncover the missing numbers.
The key to any sudoku is the arrangement of clues, or filled-in numbers, at the start. The puzzle must begin with at least enough clues to reach a unique solution using logic alone. So far no one has created a solvable puzzle with fewer than 17 clues, but this lower limit has not been mathematically proved. At the other extreme, it is technically possible to create an unsolvable puzzle with only four empty squares (see Diagram). In general, the more clues that are provided, the easier the puzzle is to solve - but there are exceptions.
Most daily newspaper sudokus provide about 28 or 30 clues. But the number matters less than the complexity of the logical leaps required to fill in the blanks. The easiest approach is to scan the rows and columns systematically to find numbers which can only fit into one possible square. Trickier sudoku puzzles require more sophisticated deductive techniques, some of which have acquired their own terminology, including naked pairs, x-wings and swordfish.

Posted: Paz - Mart 26, 2006 at 07:56 AM          

©