Sudoku
Overview
 
is a logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

-based, combinatorial number-placement puzzle
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...

. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

Completed puzzles are always a type of Latin square
Latin square
In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...

 with an additional constraint on the contents of individual regions.
Encyclopedia
is a logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

-based, combinatorial number-placement puzzle
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...

. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

Completed puzzles are always a type of Latin square
Latin square
In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...

 with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same 9×9 playing board row or column or in any of the nine 3×3 subregions of the 9×9 playing board.

The puzzle was popularized in 1986 by the Japanese puzzle company Nikoli
Nikoli
Nikoli Co., Ltd. is a Japanese publisher that specializes in games and, especially, logic puzzles. Nikoli is also the nickname of a quarterly magazine issued by the company...

, under the name Sudoku, meaning single number. It became an international hit in 2005.

History

Number puzzles appeared in newspapers in the late 19th century, when French puzzle setters began experimenting with removing numbers from magic squares. Le Siècle, a Paris-based daily, published a partially completed 9×9 magic square with 3×3 sub-squares on November 19, 1892. It was not a Sudoku because it contained double-digit numbers and required arithmetic rather than logic to solve, but it shared key characteristics: each row, column and sub-square added up to the same number.

On July 6, 1895, Le Siècle's rival, La France, refined the puzzle so that it was almost a modern Sudoku. It simplified the 9×9 magic square puzzle so that each row, column and broken diagonal
Broken diagonal
A broken diagonal is a sequence of n diametrically-positioned cells in a panmagic square which spans the vertical boundary. Examples of broken diagonals from the below square are as follows: 3,12,14,5; 10,1,7,16; 10,13,7,4; 15,8,2,9; 15,12,2,5; and 6,13,11,4....

s contained only the numbers 1–9, but did not mark the sub-squares. Although they are unmarked, each 3×3 sub-square does indeed comprise the numbers 1–9 and the additional constraint on the broken diagonals leads to only one solution.

These weekly puzzles were a feature of French newspapers such as L'Echo de Paris for about a decade but disappeared about the time of World War I
World War I
World War I , which was predominantly called the World War or the Great War from its occurrence until 1939, and the First World War or World War I thereafter, was a major war centred in Europe that began on 28 July 1914 and lasted until 11 November 1918...

.

According to Will Shortz
Will Shortz
Will Shortz is an American puzzle creator and editor, and currently the crossword puzzle editor for The New York Times.-Early life and education:...

, the modern Sudoku was most likely designed anonymously by Howard Garns
Howard Garns
Howard Garns was an American architect who gained fame only after his death as the creator of Number Place, the number puzzle that became a worldwide phenomenon under the name Sudoku.-Invention of Number Place:...

, a 74-year-old retired architect and freelance puzzle constructor from Indiana
Indiana
Indiana is a US state, admitted to the United States as the 19th on December 11, 1816. It is located in the Midwestern United States and Great Lakes Region. With 6,483,802 residents, the state is ranked 15th in population and 16th in population density. Indiana is ranked 38th in land area and is...

, and first published in 1979 by Dell Magazines
Dell Magazines
Dell Magazines was a company founded by George T. Delacorte Jr. in 1921 as part of his Dell Publishing Co. Dell is today known for its many puzzle magazines, as well as fiction magazines such as Alfred Hitchcock's Mystery Magazine, Ellery Queen's Mystery Magazine, Asimov's Science Fiction, and...

 as Number Place (the earliest known examples of modern Sudoku). Garns' name was always present on the list of contributors in issues of Dell Pencil Puzzles and Word Games that included Number Place, and was always absent from issues that did not. He died in 1989 before getting a chance to see his creation as a worldwide phenomenon. It is unclear if Garns was familiar with any of the French newspapers listed above.

The puzzle was introduced in Japan by Nikoli
Nikoli
Nikoli Co., Ltd. is a Japanese publisher that specializes in games and, especially, logic puzzles. Nikoli is also the nickname of a quarterly magazine issued by the company...

 in the paper Monthly Nikolist in April 1984 as , which can be translated as "the digits must be single" or "the digits are limited to one occurrence." (In Japanese,"dokushin" means an "unmarried person".) At a later date, the name was abbreviated to Sudoku(數獨) by , taking only the first kanji
Kanji
Kanji are the adopted logographic Chinese characters hanzi that are used in the modern Japanese writing system along with hiragana , katakana , Indo Arabic numerals, and the occasional use of the Latin alphabet...

 of compound words to form a shorter version. In 1986, Nikoli introduced two innovations: the number of givens was restricted to no more than 32, and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells
Rotational symmetry
Generally speaking, an object with rotational symmetry is an object that looks the same after a certain amount of rotation. An object may have more than one rotational symmetry; for instance, if reflections or turning it over are not counted, the triskelion appearing on the Isle of Man's flag has...

). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun
Asahi Shimbun
The is the second most circulated out of the five national newspapers in Japan. Its circulation, which was 7.96 million for its morning edition and 3.1 million for its evening edition as of June 2010, was second behind that of Yomiuri Shimbun...

.

Variants

Although the 9×9 grid with 3×3 regions is by far the most common, variations abound. Sample puzzles can be 4×4 grids with 2×2 regions; 5×5 grids with pentomino
Pentomino
A pentomino is a polyomino composed of five congruent squares, connected along their edges ....

 regions have been published under the name Logi-5; the World Puzzle Championship
World Puzzle Championship
The World Puzzle Championship is an annual international puzzle competition run by the World Puzzle Federation. The first one was held in New York in 1992...

 has featured a 6×6 grid with 2×3 regions and a 7×7 grid with six heptomino
Heptomino
A heptomino is a polyomino of order 7, that is, a polygon in the plane made of 7 equal-sized squares connected edge-to-edge. The name of this type of figure is formed with the prefix hept-. When rotations and reflections are not considered to be distinct shapes, there are 108 different free...

 regions and a disjoint region. Larger grids are also possible. The Times offers a 12×12-grid Dodeka sudoku with 12 regions of 4×3 squares. Dell regularly publishes 16×16 Number Place Challenger puzzles (the 16×16 variant often uses 1 through G rather than the 0 through F used in hexadecimal
Hexadecimal
In mathematics and computer science, hexadecimal is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen...

). Nikoli offers 25×25 Sudoku the Giant behemoths. Sudoku-zilla, a 100x100-grid was published in print in 2010.

Another common variant is to add limits on the placement of numbers beyond the usual row, column, and box requirements. Often the limit takes the form of an extra "dimension"; the most common is to require the numbers in the main diagonals of the grid also to be unique. The aforementioned Number Place Challenger puzzles are all of this variant, as are the Sudoku X puzzles in the Daily Mail
Daily Mail
The Daily Mail is a British daily middle-market tabloid newspaper owned by the Daily Mail and General Trust. First published in 1896 by Lord Northcliffe, it is the United Kingdom's second biggest-selling daily newspaper after The Sun. Its sister paper The Mail on Sunday was launched in 1982...

, which use 6×6 grids.

Mini Sudoku

A variant named "Mini Sudoku" appears in the American newspaper USA Today
USA Today
USA Today is a national American daily newspaper published by the Gannett Company. It was founded by Al Neuharth. The newspaper vies with The Wall Street Journal for the position of having the widest circulation of any newspaper in the United States, something it previously held since 2003...

 and elsewhere, which is played on a 6×6 grid with 3×2 regions. The object is the same as standard Sudoku, but the puzzle only uses the numbers 1 through 6.

Cross Sums Sudoku

Another variant is the combination of Sudoku with Kakuro on a 9×9 grid, called Cross Sums Sudoku, in which clues are given in terms of cross sums. The clues can also be given by cryptic alphametics in which each letter represents a single digit from 0 to 9. An excellent example is NUMBER+NUMBER=KAKURO which has a unique solution 186925+186925=373850. Another example is SUDOKU=IS*FUNNY whose solution is 426972=34*12558.

Killer Sudoku

Killer sudoku (also killer su doku, sumdoku, sum doku, addoku, or samunamupure) is a puzzle
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...

 that combines elements of sudoku
Sudoku
is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...

 and kakuro. Despite the name, the simpler killer sudokus can be easier to solve than regular sudokus, depending on the solver's skill at mental arithmetic; the hardest ones, however, can take hours to crack.

History

Killer sudokus were already an established variant of sudoku in Japan by the mid 1990s, where they were known as "samunamupure." The name stemmed from a Japanized form of the English words "sum number place." Killer sudokus were introduced to most of the English-speaking world by The Times
The Times
The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...

 in 2005.

Traditionally, as with regular sudoku puzzles, the grid layout is symmetrical around a diagonal, horizontal or vertical axis, or a quarter or half turn about the centre. This is a matter of aesthetics, though, rather than obligatory: many Japanese puzzle-makers will make small deviations from perfect symmetry for the sake of improving the puzzle. Other puzzle-makers may produce entirely asymmetrical puzzles.

Terminology

Cell : A single square that contains one number in the grid
Row : A horizontal line of 9 cells
Column : A vertical line of 9 cells
Nonet : A 3×3 grid of cells, as outlined by the bolder lines in the diagram above
Cage : The grouping of cells denoted by a dotted line or by individual colours.
House : Any nonrepeating set of 9 cells: can be used as a general term for "row, column, or nonet" (or, in Killer X variants, "long diagonal")

Rules

The objective is to fill the grid with numbers from 1 to 9 in a way that the following conditions are met:
  • Each row, column, and nonet contains each number exactly once.
  • The sum of all numbers in a cage must match the small number printed in its corner.
  • No number appears more than once in a cage. (This is the standard rule for killer sudokus, and implies that no cage can include more than 9 cells.)


In 'Killer X', an additional rule is that each of the long diagonals contains each number once.

Duplicate cell ambiguity

By convention in Japan, killer sudoku cages do not include duplicate numbers. However, when The Times
The Times
The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...

 first introduced the killer sudoku on 31 August 2005, the newspaper did not make this rule explicit. Even though the vast majority of killer sudoku puzzles followed the rule anyway, English-speaking solvers scratched their heads over appropriate solving strategies given the ambiguity. On September 16, 2005 The Times added a new ruling that “Within each dotted-line shape, a digit CAN be repeated if the normal row, column and 3×3 box rules are not broken”. But on September 19 the rule changed to “Within each dotted-line shape, a digit CANNOT be repeated if the normal row, column and 3×3 box rules are not broken” - causing even more scratching of heads. This revised rule stuck and the world standard is no duplicates within cages.
Fewest possible combinations

Generally the problem is best tackled starting from the extreme sums — cages with the largest or the smallest sums. This is because these have the fewest possible combinations. For example, 3 cells within the same cage totalling 23 can only be 6, 8, and 9.

In the early stages of the game, the most common way to begin filling in numbers is to look at such low-sum or high-sum cages that form a 'straight line'. As the solver can infer from these that certain numbers are in a certain row or column, he can begin 'cross-hatching' across from them.
The 45 rule

A further technique can be derived from the knowledge that the numbers in all houses (rows, columns and nonets) add up to 45
45 (number)
45 is the natural number following 44 and followed by 46.- In mathematics :Forty-five is a triangular number, a hexagonal and 16-gonal number, a Kaprekar number, and a Harshad number....

. By adding up the cages and single numbers in a particular house, the user can deduce the result of a single cell. If the cell calculated is within the house itself, it is referred to as an 'innie'; conversely if the cell is outside it, it is called an 'outie'. Even if this is not possible, advanced players may find it useful to derive the sum of two or three cells, then use other elimination techniques (see below for an example of this). The '45' technique can also be extended to calculate the innies or outies of N adjacent houses, as the difference between the cage-sums and N*45.
Initial analysis of the sample problem

Fewest possible combinations

The two cells in the top left must be 1+2. The 3 cells to the right totaling 15 cannot therefore have either a 1 or a 2, so they must be either 3+4+8, 3+5+7, or 4+5+6.

The two vertical cells in the top left of the top right nonet cannot be 2+2 as that would mean duplicates, so they must be 1+3. The 1 cannot be in the top line as that conflicts with our first 2 cells therefore the top cell of this pair is 3 and the lower cell 1. This also means the 3 cell cage 15 to the left cannot contain a 3 and so is 4+5+6.

Similarly the neighbouring 16 must be 9+7.

The four cells in the top right cage (totaling 15) can only include one of 1, 3, 7, or 9 (if at all) because of the presence of 1, 3, 7, and 9 in the top right hand nonet. If any one of 1, 3, 7, or 9 is present then this must be the lone square in the nonet below. Therefore these 4 cells is one of 1+2+4+8 or 2+3+4+6.

The 2 cells in the middle of the left edge must be either 1+5 or 2+4. And so on.
45

Looking at the nonet on the left hand side in the middle, we can see that there are three cages which do not cross over into another nonet; these add up to 33, meaning that the sum of the remaining two cells must be 12. This does not seem particularly useful, but consider that the cell in the bottom right of the nonet is part of a 3-cage of 6; it can therefore only contain 1, 2 or 3. If it contained 1 or 2, the other cell would have to contain 11 or 10 respectively; this is impossible. It must, therefore, contain 3, and the other cell 9.

Cage total tables

The following tables list the possible combinations for various sums.

2 cells
3: 12
4: 13
5: 14 23
6: 15 24
7: 16 25 34
8: 17 26 35
9: 18 27 36 45
10: 19 28 37 46
11: 29 38 47 56
12: 39 48 57
13: 49 58 67
14: 59 68
15: 69 78
16: 79
17: 89

3 cells
6: 123
7: 124
8: 125 134
9: 126 135 234
10: 127 136 145 235
11: 128 137 146 236 245
12: 129 138 147 156 237 246 345
13: 139 148 157 238 247 256 346
14: 149 158 167 239 248 257 347 356
15: 159 168 249 258 267 348 357 456
16: 169 178 259 268 349 358 367 457
17: 179 269 278 359 368 458 467
18: 189 279 369 378 459 468 567
19: 289 379 469 478 568
20: 389 479 569 578
21: 489 579 678
22: 589 679
23: 689
24: 789

4 cells
10: 1234
11: 1235
12: 1236 1245
13: 1237 1246 1345
14: 1238 1247 1256 1346 2345
15: 1239 1248 1257 1347 1356 2346
16: 1249 1258 1267 1348 1357 1456 2347 2356
17: 1259 1268 1349 1358 1367 1457 2348 2357 2456
18: 1269 1278 1359 1368 1458 1467 2349 2358 2367 2457 3456
19: 1279 1369 1378 1459 1468 1567 2359 2368 2458 2467 3457
20: 1289 1379 1469 1478 1568 2369 2378 2459 2468 2567 3458 3467
21: 1389 1479 1569 1578 2379 2469 2478 2568 3459 3468 3567
22: 1489 1579 1678 2389 2479 2569 2578 3469 3478 3568 4567
23: 1589 1679 2489 2579 2678 3479 3569 3578 4568
24: 1689 2589 2679 3489 3579 3678 4569 4578
25: 1789 2689 3589 3679 4579 4678
26: 2789 3689 4589 4679 5678
27: 3789 4689 5679
28: 4789 5689
29: 5789
30: 6789

5 cells
15: 12345
16: 12346
17: 12347 12356
18: 12348 12357 12456
19: 12349 12358 12367 12457 13456
20: 12359 12368 12458 12467 13457 23456
21: 12369 12378 12459 12468 12567 13458 13467 23457
22: 12379 12469 12478 12568 13459 13468 13567 23458 23467
23: 12389 12479 12569 12578 13469 13478 13568 14567 23459 23468 23567
24: 12489 12579 12678 13479 13569 13578 14568 23469 23478 23568 24567
25: 12589 12679 13489 13579 13678 14569 14578 23479 23569 23578 24568 34567
26: 12689 13589 13679 14579 14678 23489 23579 23678 24569 24578 34568
27: 12789 13689 14589 14679 15678 23589 23679 24579 24678 34569 34578
28: 13789 14689 15679 23689 24589 24679 25678 34579 34678
29: 14789 15689 23789 24689 25679 34589 34679 35678
30: 15789 24789 25689 34689 35679 45678
31: 16789 25789 34789 35689 45679
32: 26789 35789 45689
33: 36789 45789
34: 46789
35: 56789

6 cells

21: 123456
22: 123457
23: 123458 123467
24: 123459 123468 123567
25: 123469 123478 123568 124567
26: 123479 123569 123578 124568 134567
27: 123489 123579 123678 124569 124578 134568 234567
28: 123589 123679 124579 124678 134569 134578 234568
29: 123689 124589 124679 125678 134579 134678 234569 234578
30: 123789 124689 125679 134589 134679 135678 234579 234678
31: 124789 125689 134689 135679 145678 234589 234679 235678
32: 125789 134789 135689 145679 234689 235679 245678
33: 126789 135789 145689 234789 235689 245679 345678
34: 136789 145789 235789 245689 345679
35: 146789 236789 245789 345689
36: 156789 246789 345789
37: 256789 346789
38: 356789
39: 456789

7 cells
28: 1234567
29: 1234568
30: 1234569 1234578
31: 1234579 1234678
32: 1234589 1234679 1235678
33: 1234689 1235679 1245678
34: 1234789 1235689 1245679 1345678
35: 1235789 1245689 1345679 2345678
36: 1236789 1245789 1345689 2345679
37: 1246789 1345789 2345689
38: 1256789 1346789 2345789
39: 1356789 2346789
40: 1456789 2356789
41: 2456789
42: 3456789

8 cells
36: 12345678
37: 12345679
38: 12345689
39: 12345789
40: 12346789
41: 12356789
42: 12456789
43: 13456789
44: 23456789

9 cells
45: 123456789
6, 7, and 8 cells

It is easiest to determine the combinations within large cages by means of complements. The table for 6 cell cages is the complement of the 3 cell table adding up to 45 minus the listed value; similarly, the 7 cell table complements the 2 cell table. An 8-cell cage is of course missing only one digit (45 minus the sum of the cage).

Photo Sudoku

Photo Sudoku is a variation that allows users to play sudoku with pictures.

Alphabetical Sudoku

Alphabetical variations have emerged, sometimes called Wordoku; there is no functional difference in the puzzle unless the letters spell something. Some variants, such as in the TV Guide
TV Guide
TV Guide is a weekly American magazine with listings of TV shows.In addition to TV listings, the publication features television-related news, celebrity interviews, gossip and film reviews and crossword puzzles...

, include a word reading along a main diagonal, row, or column once solved; determining the word in advance can be viewed as a solving aid. A Wordoku might contain other words, other than the main word. Like in the example to the left, the words "Kari", "Park" and "Per" could also be found in the solution. This might be avoided by e.g. substituting the character "R" with e.g. a "Q".

A typical problem is shown on the right, using colors to define the groups of cells. More often, puzzles are printed in black and white, with thin dotted lines used to outline the "cages" (see below for terminology).

Hypersudoku

Hypersudoku is one of the most popular variants. It is published by newspapers and magazines around the world and is also known as "NRC
NRC Handelsblad
NRC Handelsblad, often abbreviated to NRC, is a daily evening newspaper published in the Netherlands by NRC Media. The newspaper was created on October 1, 1970, from merger of the Nieuwe Rotterdamsche Courant and Algemeen Handelsblad . In 2006 a morning newspaper, nrc•next, was launched...

 Sudoku", "Windoku", "Hyper-Sudoku" and "4 Square Sudoku". The layout is identical to a normal Sudoku, but with additional interior areas defined in which the numbers 1 to 9 must appear. The solving algorithm is slightly different from the normal Sudoku puzzles because of the leverage on the overlapping squares. This overlap gives the player more information to logically reduce the possibilities in the remaining squares. The approach to playing is similar to Sudoku but with possibly more emphasis on scanning the squares and overlap rather than columns and rows.

Puzzles constructed from multiple Sudoku grids are common. Five 9×9 grids which overlap at the corner regions in the shape of a quincunx
Quincunx
A quincunx is a geometric pattern consisting of five points arranged in a cross, that is five coplanar points, four of them forming a square or rectangle and a fifth at its center...

 is known in Japan as Gattai 5 (five merged) Sudoku. In The Times
The Times
The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...

, The Age
The Age
The Age is a daily broadsheet newspaper, which has been published in Melbourne, Australia since 1854. Owned and published by Fairfax Media, The Age primarily serves Victoria, but is also available for purchase in Tasmania, the Australian Capital Territory and border regions of South Australia and...

 and The Sydney Morning Herald
The Sydney Morning Herald
The Sydney Morning Herald is a daily broadsheet newspaper published by Fairfax Media in Sydney, Australia. Founded in 1831 as the Sydney Herald, the SMH is the oldest continuously published newspaper in Australia. The newspaper is published six days a week. The newspaper's Sunday counterpart, The...

 this form of puzzle is known as Samurai SuDoku. The Baltimore Sun and the Toronto Star
Toronto Star
The Toronto Star is Canada's highest-circulation newspaper, based in Toronto, Ontario, Canada. Its print edition is distributed almost entirely within the province of Ontario...

 publish a puzzle of this variant (titled High Five) in their Sunday edition. Often, no givens are to be found in overlapping regions. Sequential grids, as opposed to overlapping, are also published, with values in specific locations in grids needing to be transferred to others.

Str8ts
Str8ts
Str8ts is a logic-based number-placement puzzle, invented by Jeff Widderich in 2008. It is distinct from, but shares some properties and rules with Sudoku. The name is derived from the poker straight. The puzzle is published in a number of newspapers internationally, in 2 book collections, and in...

 shares the Sudoku requirement of uniqueness in the rows and columns but the third constraint is very different. Str8ts uses black cells (some with clue numbers) to divide the board into compartments. These must be filled with a set of numbers that form a 'straight', like the poker hand. A straight is a set of numbers with no gaps in them, such as '4,3,6,5' – and the order can be non-sequential. 9×9 is the traditional size but with suitable placement of black cells any size board is possible.
A tabletop version of Sudoku can be played with a standard 81-card Set deck (see Set game). A three-dimensional Sudoku puzzle was invented by Dion Church and published in the Daily Telegraph in May 2005. The Times
The Times
The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...

 also publishes a three-dimensional version under the name Tredoku. There is a Sudoku version of the Rubik's Cube
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...

 named Sudoku Cube.

There are many other variants. Some are different shapes in the arrangement of overlapping 9×9 grids, such as butterfly, windmill, or flower. Others vary the logic for solving the grid. One of these is Greater Than Sudoku. In this a 3×3 grid of the Sudoku is given with 12 symbols of Greater Than (>) or Less Than (<) on the common line of the two adjacent numbers. Another variant on the logic of solution is Clueless Sudoku, in which nine 9×9 Sudoku grids are themselves placed in a three-by-three array. The center cell in each 3×3 grid of all nine puzzles is left blank and form a tenth Sudoku puzzle without any cell completed; hence, "clueless".

Mathematics of Sudoku

A completed Sudoku grid is a special type of Latin square
Latin square
In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...

 with the additional property of no repeated values in any of the 9 blocks of contiguous 3×3 cells. The relationship between the two theories is now completely known, after Denis Berthier proved in his book The Hidden Logic of Sudoku (May 2007) that a first-order formula that does not mention blocks (also called boxes or regions) is valid for Sudoku if and only if it is valid for Latin Squares (this property is trivially true for the axioms and it can be extended to any formula). (Citation taken from p. 76 of the first edition: "any block-free resolution rule is already valid in the theory of Latin Squares extended to candidates" – which is restated more explicitly in the second edition, p. 86, as: "a block-free formula is valid for Sudoku if and only if it is valid for Latin Squares").

The first known calculation of the number of classic 9×9 Sudoku solution grids was posted on the USENET
Usenet
Usenet is a worldwide distributed Internet discussion system. It developed from the general purpose UUCP architecture of the same name.Duke University graduate students Tom Truscott and Jim Ellis conceived the idea in 1979 and it was established in 1980...

 newsgroup rec.puzzles in September 2003 and is 6,670,903,752,021,072,936,960 , or approximately 6.67 x 1021. This is roughly times the number of 9×9 Latin squares. A detailed calculation of this figure was provided by Bertram Felgenhauer and Frazer Jarvis in 2005. Various other grid sizes have also been enumerated—see the main article for details. The number of essentially different solutions, when symmetries
Symmetry
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...

 such as rotation, reflection, permutation and relabelling are taken into account, was shown by Ed Russell and Frazer Jarvis to be just 5,472,730,538 .

The maximum number of givens provided while still not rendering a unique solution is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy form the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be assigned. Since this applies to Latin squares in general, most variants of Sudoku have the same maximum. The inverse problem—the fewest givens that render a solution unique—is unsolved
Unsolved problems in mathematics
This article lists some unsolved problems in mathematics. See individual articles for details and sources.- Millennium Prize Problems :Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, six have yet to be solved:* P versus NP...

, 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, and 18 with the givens in rotationally symmetric cells. Over 48,000 examples of Sudokus with 17 givens resulting in a unique solution are known.

Early in 2009, Puerto Rican mathematician Francisco Javier Rodriguez, lead researcher at the Centro Chaguin de Investigación Matematicas y Filosoficas in Mayaguez, discovered a variation, called Sudoku de Calne, based on the conbíf algorithm.

In 2010 mathematicians Paul Newton and Stephen DeSalvo of the University of Southern California
University of Southern California
The University of Southern California is a private, not-for-profit, nonsectarian, research university located in Los Angeles, California, United States. USC was founded in 1880, making it California's oldest private research university...

 showed that the arrangement of numbers in Sudoku puzzles are more random than the number arrangements in randomly generated 9x9 matrices. This is because the rules of Sudoku exclude some random arrangements that have an innate symmetry.

Recent popularity

In 1997, New Zealand
New Zealand
New Zealand is an island country in the south-western Pacific Ocean comprising two main landmasses and numerous smaller islands. The country is situated some east of Australia across the Tasman Sea, and roughly south of the Pacific island nations of New Caledonia, Fiji, and Tonga...

er and retired Hong Kong
Hong Kong
Hong Kong is one of two Special Administrative Regions of the People's Republic of China , the other being Macau. A city-state situated on China's south coast and enclosed by the Pearl River Delta and South China Sea, it is renowned for its expansive skyline and deep natural harbour...

 judge Wayne Gould
Wayne Gould
Wayne Gould is a retired Hong Kong judge, most recently known for helping to popularise sudoku puzzles in the United Kingdom, and thereafter in the United States....

, then in his early 50s, saw a partly completed puzzle in a Japanese bookshop. Over six years he developed a computer program to produce puzzles quickly. Knowing that British newspapers have a long history of publishing crossword
Crossword
A crossword is a word puzzle that normally takes the form of a square or rectangular grid of white and shaded squares. The goal is to fill the white squares with letters, forming words or phrases, by solving clues which lead to the answers. In languages that are written left-to-right, the answer...

s and other puzzles, he promoted Sudoku to The Times
The Times
The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...

 in Britain, which launched it on 12 November 2004 (calling it Su Doku). The first letter to The Times regarding Su Doku was published the following day on 13 November from Ian Payn of Brentford
Brentford
Brentford is a suburban town in west London, England, and part of the London Borough of Hounslow. It is located at the confluence of the River Thames and the River Brent, west-southwest of Charing Cross. Its former ceremonial county was Middlesex.-Toponymy:...

, complaining that the puzzle had caused him to miss his stop on the tube
London Underground
The London Underground is a rapid transit system serving a large part of Greater London and some parts of Buckinghamshire, Hertfordshire and Essex in England...

.

The rapid rise of Sudoku in Britain from relative obscurity to a front-page feature in national newspapers attracted commentary in the media and parody (such as when The Guardians G2 section advertised itself as the first newspaper supplement with a Sudoku grid on every page). Recognizing the different psychological appeals of easy and difficult puzzles, The Times introduced both side by side on 20 June 2005. From July 2005, Channel 4
Channel 4
Channel 4 is a British public-service television broadcaster which began working on 2 November 1982. Although largely commercially self-funded, it is ultimately publicly owned; originally a subsidiary of the Independent Broadcasting Authority , the station is now owned and operated by the Channel...

 included a daily Sudoku game in their Teletext
Teletext
Teletext is a television information retrieval service developed in the United Kingdom in the early 1970s. It offers a range of text-based information, typically including national, international and sporting news, weather and TV schedules...

 service. On 2 August, the BBC's programme guide Radio Times
Radio Times
Radio Times is a UK weekly television and radio programme listings magazine, owned by the BBC. It has been published since 1923 by BBC Magazines, which also provides an on-line listings service under the same title...

 featured a weekly Super Sudoku which features a 16×16 grid.

In the United States, the first newspaper to publish a Sudoku puzzle by Wayne Gould was The Conway Daily Sun (New Hampshire), in 2004.

The world's first live TV Sudoku show, Sudoku Live, was a puzzle contest
Puzzle contest
Puzzle contests are popular competitions in which the objective is to solve a puzzle within a given time limit, and to obtain the best possible score among all players.-History:One of the earliest puzzle contests was held about 1910...

 first broadcast on 1 July 2005 on Sky One
Sky One
Sky1 is the flagship BSkyB entertainment channel available in the United Kingdom and Ireland.The channel first launched on 26 April 1982 as Satellite Television, and is the fourth-oldest TV channel in the United Kingdom, behind BBC One , ITV and BBC Two...

. It was presented by Carol Vorderman
Carol Vorderman
Carol Jean Vorderman MBE is a British media personality, best known for co-hosting the popular game show Countdown for 26 years from 1982 to 2008. In September 2011 she became a co-anchor of the ITV1 panel show Loose Women....

. Nine teams of nine players (with one celebrity in each team) representing geographical regions competed to solve a puzzle. Each player had a hand-held device for entering numbers corresponding to answers for four cells. Phil Kollin of Winchelsea, England was the series grand prize winner taking home over £23,000 over a series of games. The audience at home was in a separate interactive competition, which was won by Hannah Withey of Cheshire.

Later in 2005, the BBC
BBC
The British Broadcasting Corporation is a British public service broadcaster. Its headquarters is at Broadcasting House in the City of Westminster, London. It is the largest broadcaster in the world, with about 23,000 staff...

 launched SUDO-Q
SUDO-Q
SUDO-Q was a BBC quiz show hosted by Eamonn Holmes for four series between 5 December 2005 and 23 March 2007. The format was based on a mix of the number puzzle Sudoku and general knowledge questions.-Round 1:...

, a game show
Game show
A game show is a type of radio or television program in which members of the public, television personalities or celebrities, sometimes as part of a team, play a game which involves answering questions or solving puzzles usually for money and/or prizes...

 that combines Sudoku with general knowledge. However, it uses only 4×4 and 6×6 puzzles. Four seasons were produced, before the show ended in 2007.

In 2006, a Sudoku website published songwriter Peter Levy's Sudoku tribute song, but quickly had to take down the mp3 due to heavy traffic. British and Australian radio picked up the song, which is to feature in a British-made Sudoku documentary. The Japanese Embassy also nominated the song for an award, with Levy doing talks with Sony in Japan to release the song as a single.

Sudoku software is very popular on PCs, websites, and mobile phones. It comes with many distributions of Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

. Software has also been released on video game consoles, such as the Nintendo DS
Nintendo DS
The is a portable game console produced by Nintendo, first released on November 21, 2004. A distinctive feature of the system is the presence of two separate LCD screens, the lower of which is a touchscreen, encompassed within a clamshell design, similar to the Game Boy Advance SP...

, PlayStation Portable
PlayStation Portable
The is a handheld game console manufactured and marketed by Sony Corporation Development of the console was announced during E3 2003, and it was unveiled on , 2004, at a Sony press conference before E3 2004...

, the Game Boy Advance
Game Boy Advance
The is a 32-bit handheld video game console developed, manufactured, and marketed by Nintendo. It is the successor to the Game Boy Color. It was released in Japan on March 21, 2001; in North America on June 11, 2001; in Australia and Europe on June 22, 2001; and in the People's Republic of China...

, Xbox Live Arcade, the Nook
Nook
Nook may refer to a small corner formed by two walls.Nook may also refer to:*A slang name for a person reading; also known as a "book nook"*"Nook", a science-fiction TV series Lexx episode...

 e-book reader, several iPod
IPod
iPod is a line of portable media players created and marketed by Apple Inc. The product line-up currently consists of the hard drive-based iPod Classic, the touchscreen iPod Touch, the compact iPod Nano, and the ultra-compact iPod Shuffle...

 models, and the iPhone
IPhone
The iPhone is a line of Internet and multimedia-enabled smartphones marketed by Apple Inc. The first iPhone was unveiled by Steve Jobs, then CEO of Apple, on January 9, 2007, and released on June 29, 2007...

. In fact, just two weeks after Apple Inc. debuted the online App Store within its iTunes store on July 11, 2008, there were already nearly 30 different Sudoku games, created by various software developers, specifically for the iPhone and iPod Touch. One of the most popular video games featuring Sudoku is Brain Age: Train Your Brain in Minutes a Day!
Brain Age: Train Your Brain in Minutes a Day!
Brain Age: Train Your Brain in Minutes a Day!, also known as Dr. Kawashima's Brain Training: How Old Is Your Brain? in PAL regions, is an entertainment video game that employs puzzles. It was developed and published by the video gaming company Nintendo for the Nintendo DS handheld video game console...

. Critically and commercially well received, it generated particular praise for its Sudoku implementation and sold more than 8 million copies worldwide. Due to its popularity, Nintendo made a second Brain Age game titled Brain Age2, which has over 100 new Sudoku puzzles and other activities.

In June 2008 an Australia
Australia
Australia , officially the Commonwealth of Australia, is a country in the Southern Hemisphere comprising the mainland of the Australian continent, the island of Tasmania, and numerous smaller islands in the Indian and Pacific Oceans. It is the world's sixth-largest country by total area...

n drugs-related jury trial
Jury trial
A jury trial is a legal proceeding in which a jury either makes a decision or makes findings of fact which are then applied by a judge...

 costing over A$
Australian dollar
The Australian dollar is the currency of the Commonwealth of Australia, including Christmas Island, Cocos Islands, and Norfolk Island, as well as the independent Pacific Island states of Kiribati, Nauru and Tuvalu...

1,000,000 was aborted when it was discovered that five of the twelve jurors had been playing Sudoku instead of listening to evidence.

Competitions

  • The first World Sudoku Championship
    World Sudoku Championship
    The World Sudoku Championship is an annual international sudoku competition organised by a member of the World Puzzle Federation. The first one was held in Lucca in 2006. National teams are determined by local affiliates of the World Puzzle Federation...

     was held in Lucca
    Lucca
    Lucca is a city and comune in Tuscany, central Italy, situated on the river Serchio in a fertile plainnear the Tyrrhenian Sea. It is the capital city of the Province of Lucca...

    , Italy
    Italy
    Italy , officially the Italian Republic languages]] under the European Charter for Regional or Minority Languages. In each of these, Italy's official name is as follows:;;;;;;;;), is a unitary parliamentary republic in South-Central Europe. To the north it borders France, Switzerland, Austria and...

    , from March 10–12, 2006. The winner was Jana Tylová of the Czech Republic
    Czech Republic
    The Czech Republic is a landlocked country in Central Europe. The country is bordered by Poland to the northeast, Slovakia to the east, Austria to the south, and Germany to the west and northwest....

    . The competition included numerous variants.
  • The second World Sudoku Championship
    World Sudoku Championship
    The World Sudoku Championship is an annual international sudoku competition organised by a member of the World Puzzle Federation. The first one was held in Lucca in 2006. National teams are determined by local affiliates of the World Puzzle Federation...

     was held in Prague
    Prague
    Prague is the capital and largest city of the Czech Republic. Situated in the north-west of the country on the Vltava river, the city is home to about 1.3 million people, while its metropolitan area is estimated to have a population of over 2.3 million...

     from March 28 to April 1, 2007. The individual champion was Thomas Snyder
    Thomas Snyder
    Thomas Snyder is an American puzzle creator and world-champion sudoku solver. He writes a puzzle blog as Dr. Sudoku.-Early life and education:Thomas Snyder grew up in the suburbs of Buffalo, New York...

     of the USA. The team champion was Japan
    Japan
    Japan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...

    .
  • The third World Sudoku Championship
    World Sudoku Championship
    The World Sudoku Championship is an annual international sudoku competition organised by a member of the World Puzzle Federation. The first one was held in Lucca in 2006. National teams are determined by local affiliates of the World Puzzle Federation...

     was held in Goa, India, from April 14–16, 2008. Thomas Snyder
    Thomas Snyder
    Thomas Snyder is an American puzzle creator and world-champion sudoku solver. He writes a puzzle blog as Dr. Sudoku.-Early life and education:Thomas Snyder grew up in the suburbs of Buffalo, New York...

     repeated as the individual overall champion, and also won the first ever Classic Trophy (a subset of the competition counting only classic Sudoku). The Czech Republic won the team competition.
  • The fourth World Sudoku Championship
    World Sudoku Championship
    The World Sudoku Championship is an annual international sudoku competition organised by a member of the World Puzzle Federation. The first one was held in Lucca in 2006. National teams are determined by local affiliates of the World Puzzle Federation...

     was held in Žilina
    Žilina
    Žilina is a city in north-western Slovakia, around from the capital Bratislava, close to both the Czech and Polish borders. It is the fourth largest city of Slovakia with a population of approximately 85,000, an important industrial center, the largest city on the Váh river, and the seat of a...

    , Slovakia
    Slovakia
    The Slovak Republic is a landlocked state in Central Europe. It has a population of over five million and an area of about . Slovakia is bordered by the Czech Republic and Austria to the west, Poland to the north, Ukraine to the east and Hungary to the south...

    , from April 24–27, 2009. After past champion Thomas Snyder
    Thomas Snyder
    Thomas Snyder is an American puzzle creator and world-champion sudoku solver. He writes a puzzle blog as Dr. Sudoku.-Early life and education:Thomas Snyder grew up in the suburbs of Buffalo, New York...

     of USA won the general qualification, Jan Mrozowski of Poland emerged from a 36-competitor playoff to become the new World Sudoku Champion. Host nation Slovakia emerged as the top team in a separate competition of three-membered squads.
  • The fifth World Sudoku Championship
    World Sudoku Championship
    The World Sudoku Championship is an annual international sudoku competition organised by a member of the World Puzzle Federation. The first one was held in Lucca in 2006. National teams are determined by local affiliates of the World Puzzle Federation...

     was held in Philadelphia, USA from April 29 – May 2, 2010. Jan Mrozowski of Poland successfully defended his world title in the individual competition while Germany won a separate team event. The puzzles were written by Thomas Snyder
    Thomas Snyder
    Thomas Snyder is an American puzzle creator and world-champion sudoku solver. He writes a puzzle blog as Dr. Sudoku.-Early life and education:Thomas Snyder grew up in the suburbs of Buffalo, New York...

     and Wei-Hwa Huang
    Wei-Hwa Huang
    Wei-Hwa Huang is an award-winning American puzzler and member of the US Team for the World Puzzle Federation....

    , both past US Sudoku champions.
  • In the United States, The Philadelphia Inquirer Sudoku National Championship
    The Philadelphia Inquirer Sudoku National Championship
    The Philadelphia Inquirer Sudoku National Championship, hosted by puzzle master Will Shortz, is an annual sudoku competition run by The Philadelphia Inquirer and held at the Pennsylvania Convention Center....

     has been held three times, each time offering a $10,000 prize to the advanced division winner and a spot on the U.S. National Sudoku Team traveling to the world championships. Puzzlemaster Will Shortz
    Will Shortz
    Will Shortz is an American puzzle creator and editor, and currently the crossword puzzle editor for The New York Times.-Early life and education:...

     has served as tournament host. The winners of the event have been Thomas Snyder
    Thomas Snyder
    Thomas Snyder is an American puzzle creator and world-champion sudoku solver. He writes a puzzle blog as Dr. Sudoku.-Early life and education:Thomas Snyder grew up in the suburbs of Buffalo, New York...

     (2007), Wei-Hwa Huang
    Wei-Hwa Huang
    Wei-Hwa Huang is an award-winning American puzzler and member of the US Team for the World Puzzle Federation....

     (2008), and Tammy McLeod (2009). In the most recent event, the third place finalist in the advanced division, Eugene Varshavsky, performed quite poorly onstage after setting a very fast qualifying time on paper, which caught the attention of organizers and competitors including past champion Thomas Snyder who requested organizers reconsider his results due to a suspicion of cheating. Following an investigation and a retest of Varshavsky, the organizers disqualified him and awarded Chris Narrikkattu third place.

See also

  • 36 cube
    36 cube
    The 36 Cube is a three-dimensional sudoku puzzle created by ThinkFun. The puzzle consists of a gray base that resembles a city skyline, plus 36 colored towers. The towers come in six different colors and six different heights...

  • Algorithmics of Sudoku
    Algorithmics of sudoku
    The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols , so that each row, column and region contains exactly one of each element of the set...

  • Futoshiki
    Futoshiki
    or Unequal is a logic puzzle game from Japan. Its name means "inequality". It is also spelled hutosiki .The puzzle is played on a square grid, such as 5 x 5. The objective is to place the numbers 1 to 5 such that each row, and column contains each of the digits 1 to 5. Some digits may be given...

  • Hidato
    Hidato
    Hidato is a logic puzzle game invented by Dr. Gyora Benedek, an Israeli mathematician. The goal of Hidato is to fill the grid with consecutive numbers that connect horizontally, vertically, or diagonally.-About the puzzle:...

  • Kakuro
  • KenKen
    KenKen
    KenKen or KenDoku is a style of arithmetic and logic puzzle invented in 2004 by the Japanese math teacher Tetsuya Miyamoto, an innovator who says he practices "the art of teaching without teaching". He intends the puzzles as an instruction-free method of training the brain...

  • List of Nikoli puzzle types
  • List of Sudoku terms and jargon
  • Logic puzzle
    Logic puzzle
    A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...

  • Mathematics of Sudoku
    Mathematics of Sudoku
    The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions each of size N cells, to be filled in using a prescribed set of N distinct symbols , so that each row, column and region contains exactly one of each element of the set...

  • Nonogram (aka Paint by numbers, O'ekaki)
  • Str8ts
    Str8ts
    Str8ts is a logic-based number-placement puzzle, invented by Jeff Widderich in 2008. It is distinct from, but shares some properties and rules with Sudoku. The name is derived from the poker straight. The puzzle is published in a number of newspapers internationally, in 2 book collections, and in...

     sequential numbers

Further reading

  • Delahaye, Jean-Paul, "The Science Behind Sudoku", Scientific American
    Scientific American
    Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...

     magazine, June 2006.
  • Kim, Scott
    Scott Kim
    Scott Kim is an American puzzle and computer game designer, artist, and author. He started writing an occasional "Boggler" column for Discover magazine in 1990, and became an exclusive columnist in 1999, and created hundreds of other puzzles for magazines such as Scientific American and Games, as...

    , "The Science of Sudoku", 2006
  • Provan, J. Scott, "Sudoku: Strategy Versus Structure", American Mathematical Monthly, October 2009. Published also as a University of North Carolina
    University of North Carolina
    Chartered in 1789, the University of North Carolina was one of the first public universities in the United States and the only one to graduate students in the eighteenth century...

     technical report UNC/STOR/08/04, 2008.

External links

– An active listing of Sudoku links.
  • 'Father of Sudoku' puzzles next move BBC
    BBC
    The British Broadcasting Corporation is a British public service broadcaster. Its headquarters is at Broadcasting House in the City of Westminster, London. It is the largest broadcaster in the world, with about 23,000 staff...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK