About Sudoku

Sudoku, sometimes spelled Su Doku, is a logic-based placement puzzle, also known as Number Place in the United States. The aim of the canonical puzzle is to enter a numeral from 1 through 9 in each cell of a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various numerals given in some cells (the "givens"). Each row, column and region must contain only one instance of each numeral. Completing the puzzle requires patience and logical ability. Its grid layout is reminiscent of other newspaper puzzles like crosswords and chess problems. Although first published in 1979, Sudoku initially became popular in Japan in 1986 and attained international popularity in 2005.

The word Sudoku means "numbers singly" in Japanese. (This name is a registered trademark of puzzle publisher Nikoli Co. Ltd in Japan, and other Japanese publishers generally refer to it as "number place". See History section, below.) The numerals in Sudoku puzzles are used for convenience; arithmetic relationships between numerals are absolutely irrelevant. Any set of distinct symbols will do; letters, shapes, or colours may be used without altering the rules (Penny Press' Scramblets and Knight Features Syndicate's Sudoku Word both use letters). Dell Magazines, the puzzle's originator, has been using numerals for Number Place in its magazines since they first published it over 25 years ago. Numerals are used throughout this article.

The attraction of the puzzle is that the completion rules are simple, yet the line of reasoning required to reach the completion may be difficult. Sudoku is recommended by some teachers as an exercise in logical reasoning. The level of difficulty of the puzzles can be selected to suit the audience. The puzzles are often available free from published sources and also may be custom-generated using software.

Go To Top 

The puzzle is most frequently a 9×9 grid, made up of 3×3 subgrids called "regions" (other terms include "boxes", "blocks", and the like when referring to the standard variation). Some cells already contain numbers, known as "givens" (or sometimes as "clues"). The goal is to fill in the empty cells, one number in each, so that each column, row, and region contains the numbers 1–9 exactly once. Each number in the solution therefore occurs only once in each of three "directions", hence the "single numbers" implied by the puzzle's name.

Go To Top 

The strategy for solving a puzzle may be regarded as comprising a combination of three processes: scanning, marking up, and analysing.

Go To Top 

Published puzzles often are ranked in terms of difficulty. Perhaps surprisingly, the number of givens has little or no bearing on a puzzle's difficulty. A puzzle with a minimum number of givens may be very easy to solve, and a puzzle with more than the average number of givens can still be extremely difficult to solve. Computer solvers can estimate the difficulty for a human to find the solution, based on the complexity of the solving techniques required. This estimation allows publishers to tailor their Sudoku puzzles to audiences of varied solving experience. Some online versions offer several difficulty levels.

Go To Top 

It is possible to set starting grids with more than one solution and to set grids with no solution, but such are not considered proper Sudoku puzzles; like most other pure-logic puzzles, a unique solution is expected.

Building a Sudoku by hand can be performed efficiently by pre-determining the locations of the givens and assigning them values only as needed to make deductive progress. Such an undefined given can be assumed to not hold any particular value as long as it is given a different value before construction is completed; the solver will be able to make the same deductions stemming from such assumptions, as at that point the given is very much defined as something else. This technique gives the constructor greater control over the flow of puzzle solving, leading the solver along the same path the puzzlesmith used in building the puzzle. (This technique is adaptable to composing puzzles other than Sudoku as well.) Great caution is required, however, as failing to recognize where a number can be logically deduced at any point in construction—regardless of how tortuous that logic may be—can result in an unsolvable puzzle when defining a future given contradicts what has already been built. Building a Sudoku with symmetrical givens is a simple matter of placing the undefined givens in a symmetrical pattern to begin with.

It is commonly believed that Dell Number Place puzzles are computer-generated; they typically have over 30 givens placed in an apparently random scatter, some of which can possibly be deduced from other givens. They also have no authoring credits — that is, the name of the constructor is not printed with any puzzle. Wei-Hwa Huang claims that he was commissioned by Dell to write a Number Place puzzle generator in the winter of 2000; prior to that, he was told, the puzzles were hand-made. The puzzle generator was written with Visual C++, and although it had options to generate a more Japanese-style puzzle, with symmetry constraints and fewer numbers, Dell opted not to use those features, at least not until their recent publication of Sudoku-only magazines.

Nikoli Sudoku are hand-constructed, with the author being credited beside each puzzle; the givens are always found in a symmetrical pattern. Dell Number Place Challenger (see Variants below) puzzles also list author credits. The Sudoku puzzles printed in most UK newspapers are apparently computer-generated but employ symmetrical givens; The Guardian licenses and publishes Nikoli-constructed Sudoku puzzles, though it does not include authoring credits. The Guardian famously claimed that because they were hand-constructed, their puzzles would contain "imperceptible witticisms" that would be very unlikely in computer-generated Sudoku. The challenge to Sudoku programmers is teaching a program how to build clever puzzles, such that they may be indistinguishable from those constructed by humans; Wayne Gould required six years of tweaking his popular program before he believed he achieved that level.

Go To Top 

Although the 9×9 grid with 3×3 regions is by far the most common, numerous variations abound: sample puzzles can be 4×4 grids with 2×2 regions; 5×5 grids with pentomino regions have been published under the name Logi-5; the World Puzzle Championship has previously featured a 6×6 grid with 2×3 regions and a 7×7 grid with six heptomino regions and a disjoint region. Even the 9×9 grid is not always standard, with Ebb regularly publishing some of those with nonomino regions. Larger grids are also possible, with Dell regularly publishing 16×16-grid Number Place Challenger puzzles and Nikoli proffering 25×25 Sudoku the Giant behemoths. Another common variant is for the numbers in the main diagonals of the grid to also be required to be unique; the aforementioned Number Place Challenger puzzles are all of this variant, as are the Sudoku X puzzles in the Daily Mail, which use 6×6 grids. The Daily Mail also features Super Sudoku X in its Weekend magazine: an 8×8 grid in which rows, columns, main diagonals, 2×4 blocks and 4×2 blocks contain each number once.

Five 9×9 grids which overlap at the corner regions in the shape of a quincunx is known in Japan as Gattai 5 (five merged) Sudoku. In The Times this form of puzzle is known as Samurai Su Doku. [1]

A three-dimensional Sudoku puzzle was invented by Dion Church and published in the Daily Telegraph in May 2005.

Alphabetical variations, which use letters rather than numbers, have also emerged. The Guardian calls these Godoku and describes them as "devilish". Knight Features uses the term Sudoku Word [2]. In Top Notch's Wordoku [3] the required letters are given beneath the puzzle - once arranged they spell out a topical word between the top left and bottom right corners. This adds an extra dimension to Sudoku as it may be possible to guess what the word is, indicating what some of the unfilled cells might be.

The Code Doku[4] devised by Steve Schaefer has an entire sentence embedded into the puzzle while the Super Wordoku[5] from Top Notch embeds two 9-letter words, one on each diagonal. It is debatable as to whether the Super Wordoku puzzles and some (but not all) of the Code Doku puzzles are true Sudoku puzzles, because although they have a single valid solution, they cannot be solved entirely by Sudoku logic, and the solver must rely on deducing the embedded words. Top Notch claim this as a feature designed to defeat solver programs.

Kokonotsu (a Japanese word that simply means nine) has been dubbed "SuperSudoku" by its creators. It adds dimensions and challenges not found in ordinary Sudoku. While generic Sudoku puzzles only require the player to fill in rows, columns and 3×3 boxes, Kokonotsu adds 4th and 5th dimensions: the two diagonals and a "Magic Puzzle Heart" consisting also of nine numbers that players may find and use to help them solve the puzzle more quickly.

Other variants common in Japanese magazines include, but are not limited to:

• Sequentially connected puzzles: several standard 9×9 puzzles are solved consecutively. Only the first puzzle has enough givens to be solved on its own; once the first puzzle is solved, one or more numbers are transferred from its solution to the starting grid of the second, etc. In some cases, the solver must work back and forth between partially completed puzzles.
• Very large puzzles made up of multiple overlapping puzzles (usually, but not always, 9×9s). Puzzles made up of 20 to 50 or more standard grids are not uncommon. The region of overlap varies—two 9×9s may share 9, 18, or 36 cells. Often, there are no givens in overlapped areas.
• Otherwise standard puzzles in which each cell is a member of four groups rather than the normal three (rows, columns, and regions): digits with the same relative location within their respective regions must not match. Such puzzles are usually printed in colour, with each disjoint group sharing one colour for clarity.

The 2005 U.S. qualifier for the World Puzzle Championship includes a variant called Digital Number Place: rather than givens, most cells contain a partial given—a segment of a number, with the numbers drawn as if part of a seven-segment display.

On 31 August 2005, The Times started publishing what it branded as Killer Su Doku, or Samunamupure (meaning sum number place), where instead of individual starting numbers, squares are grouped and the sum of the values is given, adding an extra layer of complexity and further dependencies to track, although it can also assist, by providing further constraints on the numbers that can be placed. Aside from this the normal Sudoku rules apply. Easy versions have "groups" of one square, which is basically giving the value, as in standard Sudoku.

Go To Top 

The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete [6]. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.

Solving Sudoku puzzles can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labelled with the ordered pairs (x,y), where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by (x,y) and (x^l,y^l) are joined by an edge if and only if:

x = x^l or,

y = y^l or,

[x/3] = [x^l/3] and [y/3] = [y^l/3]

The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.

A valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960 [7] (sequence A107739 in OEIS). This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions [8] (sequence A109741 in OEIS). The number of valid Sudoku solution grids for the 16×16 derivation is not known.

The maximum number of givens that can be provided while still not rendering the solution unique, regardless of variation, is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy are the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be added. The inverse of this—the fewest givens that render a solution unique—is an unsolved problem, although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts [9] [10], and 18 with the givens in rotationally symmetric cells.

For more results and conjectures, see the Mathematics of Sudoku page.

Go To Top 

Originally called simply Number Place, the first puzzle was created by Howard Garns, a freelance puzzle constructor, in 1979. The puzzle was first published in New York in the late 1970s by the specialist puzzle publisher Dell Magazines in its magazine Dell Pencil Puzzles and Word Games, under the title Number Place. The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as "Suji wa dokushin ni kagiru (????????)", which can be translated as "the numbers must be single" or "the numbers must occur only once" (?? literally means "single; celibate; unmarried"). The puzzle was named by Kaji Maki (?? ??), the president of Nikoli. At a later date, the name was abbreviated to Sudoku (??, pronounced sue-do-koo; su = number, doku = single); it is a common practice in Japanese to take only the first kanji of compound words to form a shorter version. In 1986, Nikoli introduced two innovations which guaranteed the popularity of the puzzle: the number of givens was restricted to no more than 30 and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun. Within Japan, Nikoli still holds the trademark for the name Sudoku; other publications in Japan use alternative names.

In 1989, Loadstar/Softdisk Publishing published DigitHunt on the Commodore 64, which was apparently the first home computer version of Sudoku. At least one publisher still uses that title.

Yoshimitsu Kanai published his computerized puzzle generator under the name Single Number (the English translation of 'sudoku') for the Apple Macintosh [11] in 1995 in Japanese and English, and in 1996 for the Palm (PDA) [12].

Bringing the process full-circle, Dell Magazines, which publishes the original Number Place puzzle, now also publishes two Sudoku magazines: Original Sudoku and Extreme Sudoku. Additionally, Kappa reprints Nikoli Sudoku in GAMES Magazine under the name Squared Away; the New York Post, USA Today, and San Francisco Chronicle now also publish the puzzle. It is also often included in puzzle anthologies, such as The Giant 1001 Puzzle Book (under the title Nine Numbers).

Within the context of puzzle history, parallels are often cited to Rubik's Cube, another logic puzzle popular in the 1980s. Sudoku has been called the "Rubik's cube of the 21st century".

Go To Top