Sudoku puzzles

A Sudoku puzzle (image hyperlinked to solution). Sudoku (数独, sūdoku?), also known as Number Place or Nanpure, is a logic-based placement puzzle. The aim of the puzzle is to enter a numerical digit from 1 through 9 in each cell of a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various digits 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. An early variant of the puzzle was published in a French newspaper in 1895 and may have been influenced by the great Swiss mathemetician Leonhard Euler, who repopularized Latin squares. Though Euler is frequently misrepresented as being the origin of either game, in fact Latin Squares are frequently engraved in architecture as a numerological talisman, some several thousand years old; and Euler made no changes to their rules. Arabic Numerologists had already compiled an exhaustive list of order 3 through order 9 Greco-Latin Squares in the Jabirean Corpus by 990 AD. The modern game Sudoku was invented in Indianapolis in 1979. Interest in Sudoku stems from a revival in Japan in 1986, when the venerable puzzle publisher Nikoli discovered the game as invented by Howard Garns and initially distributed for children under the name "Number Place" in an older Dell Magazines publication, and republished the format leading to widespread international popularity in 2005. Contents 1 Introduction 2 Gameplay 3 Solution methods 3.1 Scanning 3.2 Marking up 3.3 Analysis 3.3.1 Candidate elimination 3.3.2 The "What-If" Approach 3.4 Computer solutions 4 Difficulty ratings 5 Construction 6 Variants 7 Mathematics of Sudoku 8 History 8.1 Popularity in the media 9 See also 10 References 11 External links Introduction The name "Sudoku" is the Japanese abbreviation of a longer phrase, "Suuji wa dokushin ni kagiru" (数字は独身に限る, "Suuji wa dokushin ni kagiru"?), meaning "the digits must remain single". It is a trademark of puzzle publisher Nikoli Co. Ltd. in Japan. In Japanese, the word is pronounced [sɯːdokɯ]; in English, it is usually spoken with an Anglicised pronunciation, [səˈdəʊkuː] (BrE) [səˈdoʊkuː] (AmE) or [ˈsuːdəʊku] (BrE) [ˈsuːdoʊku] (AmE) (See IPA (International Phonetic Alphabet) or IPA chart for English for notation usage.) Other Japanese publishers refer to the puzzle as Number Place, the original U.S. title, or as "Nampure" for short. Some non-Japanese publishers spell the title as "Su Doku". The numerals in Sudoku puzzles are used for convenience; arithmetic relationships between numerals are 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). In fact, ESPN has published Sudoku puzzles that substitute the positions on a baseball field for the numbers 1-9. Dell Magazines, the puzzle's originator, has been using numerals for Number Place in its magazines since they first published it in 1979. Numerals are used throughout this article. The attraction of the puzzle is that the rules are simple, yet the line of reasoning required to reach the solution may be complex. 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 may also be custom-generated using software. Gameplay 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; even "quadrants" is sometimes used, despite this being an inaccurate term for a 9×9 grid). Some cells already contain numerals, known as "givens" (or sometimes as "clues"). The goal is to fill in the empty cells, one numeral in each, so that each column, row, and region contains the numerals 1–9 exactly once. Each numeral in the solution therefore occurs only once in each of three "directions" or "scopes", hence the "single numbers" implied by the puzzle's name. Solution methods The strategy for solving a puzzle may be regarded as comprising a combination of three processes: scanning, marking up, and analyzing. The 3×3 region in the top-right corner must contain a 5. By hatching across and up from 5s located elsewhere in the grid, the solver can eliminate all of the empty cells in the top-right corner which cannot contain a 5. This leaves only one possible cell for a 5 (highlighted in green). Scanning Scanning is performed at the outset and throughout the solution. Scans only have to be performed one time in between analysis periods. Scanning consists of two basic techniques: Cross-hatching: the scanning of rows (or columns) to identify which line in a particular region may contain a certain numeral by a process of elimination. This process is then repeated with the columns (or rows). For fastest results, the numerals are scanned in order of their frequency. It is important to perform this process systematically, checking all of the digits 1–9. Counting 1–9 in regions, rows, and columns to identify missing numerals. Counting based upon the last numeral discovered may speed up the search. It also can be the case (typically in tougher puzzles) that the easiest way to ascertain the value of an individual cell is by counting in reverse—that is, by scanning the cell's region, row, and column for values it cannot be, in order to see which is left. Advanced solvers look for "contingencies" while scanning—that is, narrowing a numeral's location within a row, column, or region to two or three cells. When those cells all lie within the same row (or column) and region, they can be used for elimination purposes during cross-hatching and counting (Contingency example at Puzzle Japan). Particularly challenging puzzles may require multiple contingencies to be recognized, perhaps in multiple directions or even intersecting—relegating most solvers to marking up (as described below). Puzzles that can be solved by scanning alone without requiring the detection of contingencies are classified as "easy" puzzles; more difficult puzzles, by definition, cannot be solved by basic scanning alone. Candidates for each empty cell have been entered. Some cells have only one candidate once obvious invalids have been excluded. Also, some mark with dots instead of numbers, simply using the position of the dot within the cell to distinguish them. (Click the image to see a larger one). A method for marking likely numerals in a single cell by the placing of pencil dots. To reduce the number of dots used in each cell, the marking would only be done after as many numbers as possible have been added to the puzzle by scanning. Dots are erased as their corresponding numerals are eliminated as candidates. Marking up Scanning stops when no further numerals can be discovered. From this point, it is necessary to engage in some logical analysis. Many find it useful to guide this analysis by marking candidate numerals in the blank cells. There are two popular notations: subscripts and dots. In the subscript notation the candidate numerals are written in subscript in the cells. The drawback to this is that original puzzles printed in a newspaper usually are too small to accommodate more than a few digits of normal handwriting. If using the subscript notation, solvers often create a larger copy of the puzzle or employ a sharp or mechanical pencil. The second notation uses a pattern of dots within each square, where the position of the dot represents a number from 1 to 9. Dot schemes differ and one method is illustrated here. The dot notation has the advantage that it can be used on the original puzzle. Dexterity is required in placing the dots, since misplaced dots or inadvertent marks inevitably lead to confusion and may not be easy to erase without adding to the confusion. Using a sharp pencil with an eraser end is recommended. An alternative technique, that some find easier, is to "mark up" those numerals that a cell cannot be. Thus a cell will start empty and as more constraints become known it will slowly fill. When only one mark is missing, that has to be the value of the cell. One advantage to this method of marking is that, assuming no mistakes are made and the marks can be overwritten with the value of a cell, there is no longer a need for any erasures. When using marking, additional analysis can be performed. For example, if a digit appears only one time in the mark-ups written inside one region, then it is clear that the digit should be there, even if the cell has other digits marked as well. Analysis The two main approaches to analysis are "candidate elimination" and "what-if". Candidate elimination In "candidate elimination", progress is made by successively eliminating candidate numerals from one or more cells to leave just one choice. After each answer has been achieved, another scan may be performed—usually checking to see the effect of the contingencies. One method of candidate elimination works by identifying "matched cells". Cells are said to be matched within a particular row, column, or region (scope) if two cells contain the same pair of candidate numerals (p,q) and no others, or if three cells contain the same triplet of candidate numerals (p,q,r) and no others. The placement of these numerals anywhere else within that same scope would make a solution for the matched cells impossible; thus, the candidate numerals (p,q,r) appearing in unmatched cells in that same row, column or region (scope) can be deleted. This principle also works with candidate numeral subsets, that is, if three cells have candidates (p,q,r), (p,q), and (q,r) or even just (p,r), (q,r), and (p,q), all of the set (p,q,r) elsewhere within that same scope can be deleted. The principle is true for all quantities of candidate numerals. A second related principle is also true. If, within any set of cells (row, column or region), a set of candidate numerals can only appear within a number of cells equal to the quantity of candidate numerals, the cells and numerals are matched and only those numerals can appear in the matched cells. Other candidates in the matched cells can be eliminated. For example, if the 2 numerals (p,q) can only appear in 2 cells within a specific set of cells (row, column or region), all other candidates in those 2 cells can be eliminated. The first principle is based on cells where only matched numerals appear. The second is based on numerals that appear only in matched cells. The validity of either principle is demonstrated by posing the question, 'Would entering the eliminated numeral prevent completion of the other necessary placements?' If the answer to the question is 'Yes,' then the candidate numeral in question can be eliminated. Advanced techniques carry these concepts further to include multiple rows, columns, and regions. The "What-If" Approach In the "what-if" approach (also called "guess-and-check", "bifurcation", and "Ariadne's thread"), a cell with only two candidate numerals is selected, and a guess is made. The steps above are repeated unless a duplication is found or a cell is left with no possible candidate, in which case the alternative candidate must be the solution. In logic, this is known as reductio ad absurdum. Nishio is a limited form of this approach: for each cell's candidate, the question is posed: 'will entering a particular numeral prevent completion of the other placements of that numeral?' If the answer is 'yes', then that candidate can be eliminated. The what-if approach requires a pencil and eraser. This approach may be frowned on by logical purists as trial and error (and most published puzzles are built to ensure that it is not necessary to resort to this tactic), but it can arrive at solutions fairly rapidly. Ideally one needs to find a combination of techniques that avoids some of the drawbacks of the above elements. The counting of regions, rows, and columns can become boring. Writing candidate numerals into empty cells can be time-consuming. The what-if approach can be confusing unless you are well organised. The proverbial Holy Grail is to find a technique that minimizes counting, marking up, and rubbing out. Computer solutions Although a simple Ariadne's thread (depth-first search) algorithm can solve (or prove invalid) any Sudoku puzzle, it is computationally inefficient and as such rarely employed on its own. There are two general approaches taken in the creation of serious Sudoku-solving programs: emulate the human solving method as closely as possible, which allows for determining the difficulty level of an inputted puzzle; solve puzzles as efficiently as possible, which allows for faster computation. Either way, a computer program is capable of exhaustively searching a Sudoku puzzle for solutions, thereby determining whether it is valid (has exactly one solution) or not, with great ease relative to a human attempting the same. Human-style solvers will typically operate by maintaining a mark-up matrix identical to that which a human solver may use (see "Marking up" under "Solution methods" above), and search for contingencies, matched cells, and other elements that a human solver can utilize in order to determine and exclude cell values, resorting to Ariadne's thread only as a last resort. Each type of operation performed can be assigned a difficulty value; the sum of these values can be construed as a difficulty level of the puzzle. Many rapid-style solvers still employ backtracking searches, but with various shortcuts and optimizations to reduce the width of the search tree; which techniques are superior is under frequent debate. Another alternative uses finite domain constraint programming. A constraint program specifies the constraints of the puzzle (the fact that every number in each row, each column, and each 3×3 region must be unique, and the provided "givens"); a finite-domain solver applies the constraints successively to narrow down the solution space until a solution is found. Backtracking may be applied when alternate values cannot otherwise be excluded. Although for standard Sudoku problems highly-optimized and sophisticated backtracking programs are the most efficient, another popular way of solving such constraint problems is Donald Knuth's Dancing Links Algorithm for solving the exact matrix cover problem, of which the Sudoku problems are a special case. Knuth's algorithm can be applied by converting the Sudoku puzzle to a matrix cover problem, solve this problem instead, and convert the solution obtained back to a completed Sudoku grid. This method is now preferred by many Sudoku programmers, by virtue of its execution speed, simplicity and ease of implementation, and the availability of documentation and reference source code. Rapid solvers are preferred for trial-and-error puzzle-creation algorithms, which allow for testing large numbers of partial problems for validity in a short time; human-style solvers can be employed by hand-crafting puzzlesmiths for their ability to rate the challenge of a created puzzle and show the actual solving process their target audience can be expected to follow. Difficulty ratings Published puzzles often are ranked in terms of difficulty. Surprisingly, the number of givens does not always reflect 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 can still be extremely difficult. The difficulty of a puzzle is based on the relevance and the positioning of the given numbers rather than their quantity. 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. Most publications sort their Sudoku puzzles into four or five rating levels, although the actual cut-off points of the levels and indeed the names of the levels themselves can vary widely. Typically, however, the titles are some set of synonyms of "easy", "intermediate", "hard", and "challenging". Another approach is to rely on the experience of a group of human test solvers. Puzzles can be published with a stated median solving time rather than an algorithmically defined difficulty level. Construction 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; as in most other pure-logic puzzles, a unique solution is expected. Building a Sudoku puzzle 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 compiler 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 handmade. 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; the givens are always found in a symmetrical pattern. Dell Number Place Challenger (see Variants below) puzzles also list authors. 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 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. Variants A nonomino Sudoku puzzle An extra-regions Sudoku puzzle (Source: NRC Handelsblad) 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 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; Daily SuDoku features new 4×4, 6×6, and simpler 9×9 grids every day as Daily SuDoku for Kids. [1] Even the 9×9 grid is not always standard, with Ebb regularly publishing some of those with nonomino regions (also known as a jigsaw variation); the 2005 U.S. Puzzle Championship had a Sudoku with parallelogram regions that wrapped around the outer border of the puzzle, as if the grid were toroidal. Larger grids are also possible, with Daily SuDoku's 16×16-grid Monster SuDoku [2], the Times likewise offers a 12×12-grid Dodeka sudoku with 12 regions each being 4×3, Dell regularly publishing 16×16 Number Place Challenger puzzles (the 16×16 variant often uses 1 through G rather than the 0 through F used in hexadecimal), and Nikoli proffering 25×25 Sudoku the Giant behemoths. Another common variant is for additional restrictions to be enforced on the placement of numbers beyond the usual row, column, and region requirements. Often the restriction takes the form of an extra "dimension"; the most common 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. Another dimension in use is digits with the same relative location within their respective regions; such puzzles are usually printed in colour, with each disjoint group sharing one colour for clarity. Also common are puzzles that are otherwise standard but include extra regions overlapping the usual nine, be they square (as published every Saturday in the Dutch NRC Handelsblad) or otherwise (see final puzzle of "Sudoku Variations" article in References). Chess-themed variants have also arisen, all of which fit this category; certain numerals are replaced with chess pieces, whose attack ranges are translated into extra regions and/or additional placement restrictions. Any of these means of increasing restrictions tends to reduce the number of givens required to render a puzzle valid (has exactly one solution). Other kinds of extra restrictions can be arithmetical in nature, such as requiring the numbers in delineated segments of the grid to have specific sums or products (an example of the former being Killer Su Doku in The Times), demarcating all places arithmetically adjacent digits appear orthogonally adjacent in the grid, providing the parity of all cells, requiring the Lo Shu Square to appear in the solution, and so on. Some such variants forsake standard givens entirely. Puzzles constructed from multiple Sudoku grids are common. 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 and The Sydney Morning Herald this form of puzzle is known as Samurai SuDoku. [3] Puzzles with twenty or more overlapping grids are not uncommon in some Japanese publications. 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. Alphabetical variations have also emerged; there is no functional difference in the puzzle unless the letters spell something. Some variants, such as in the TV Guide, 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. The Code Doku [4] devised by Steve Schaefer has an entire sentence embedded into the puzzle; the Super Wordoku [5] from Top Notch embeds two 9-letter words, one on each diagonal. It is debatable whether these are true Sudoku puzzles: although they purportedly have a single linguistically valid solution, they cannot necessarily be solved entirely by logic, requiring the solver to determine the embedded words. Top Notch claim this as a feature designed to defeat solving programs. Other variant of sudoku is sidoku where instead of numbers there are musical notes. Here are some of the more notable single-instance variations: A three-dimensional Sudoku puzzle was invented by Dion Church and published in the Daily Telegraph in May 2005. The 2005 U.S. 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. Wei-Hwa Huang created a meta-Sudoku, where the object is to finish drawing the 5×5 grid's pentomino-region borders so as to leave a uniquely solvable puzzle with no identically-shaped regions. Michael Metcalf reportedly created a 100×100 Sudoku puzzle, published to the "Sudokuworld" Yahoo! group. The online linguistics journal Speculative Grammarian published a simple 3x3 Sudoku-like puzzle called "LingDoku", which requires the solver to solve for two variables at once. Mathematics of Sudoku Main article: Mathematics of Sudoku The general problem of solving Sudoku puzzles on n² × n² boards of n × 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 (as well as any other NP-hard problem) 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 , where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by and are joined by an edge if and only if: or, or, and 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 completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any 3×3 block. The number of classic 9×9 Sudoku solution grids was shown in 2005 by Bertram Felgenhauer and Frazer Jarvis to be 6,670,903,752,021,072,936,960 [7] (sequence A107739 in OEIS) : this is roughly 0.00012% the number of 9×9 Latin squares. Various other grid sizes have also been enumerated -- see the main article for details. The number of essentially different solutions, when symmetries such as rotation, reflection and relabelling are taken into account, was shown by Ed Russell and Frazer Jarvis to be just 5,472,730,538 [8] (sequence A109741 in OEIS). Both results have been confirmed by independent authors. The maximum number of givens that can be provided while still not rendering the solution unique 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, 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. History Page from Le Siècle newspaper, November 19, 1892 Page from La France newspaper, July 6, 1895 Number puzzles have been appearing in newspapers for well over a century. Le Siècle, a French daily, produced a 9x9 grid with 3x3 sub-squares as early as 1892, but used double-digit numbers rather than the familiar 1-9 [11]. In 1895, another French daily, La France, created a puzzle that used the numbers 1-9 but did not mark the 3x3 sub-squares (although the solution does indeed have 1-9 in each of the 3x3 areas where the sub-squares would be). These puzzles, printed weekly, were a feature of newspaper titles including L'Echo de Paris for about a decade but disappeared at about the time of the First World War.[12] The modern Sudoku was designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor, and first published in 1979.[1] Garns added a third dimension (the regional restriction) to the traditional Roman practice of Latin Squares and presented the creation as a puzzle, providing a partially-completed grid and requiring the solver to fill in the rest. The puzzle was first published in New York 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 Suuji wa dokushin ni kagiru (数字は独身に限る, Suuji 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 Maki Kaji (鍜治 真起, Kaji Maki?), the president of Nikoli. At a later date, the name was abbreviated to Sudoku, taking only the first kanji of compound words to form a shorter version. In 1986, Nikoli introduced two innovations that guaranteed the popularity of the puzzle: the number of givens was restricted to no more than 32 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 for the Apple Macintosh [13] in 1995 in Japanese and English, for the Palm (PDA) [14] in 1996, and for Mac OS X [15] in 2005. 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, The Boston Globe, Washington Post, The Examiner, 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". Popularity in the media In 1997, retired Hong Kong judge Wayne Gould, 59, a New Zealander, saw a partly completed puzzle in a Japanese bookshop. Over 6 years he developed a computer program to produce puzzles quickly. Knowing that British newspapers have a long history of publishing crosswords and other puzzles, he promoted Sudoku to The Times in Britain, which launched it on 12 November 2004 (calling it Su Doku). The puzzles by Pappocom, Gould's software house, have been printed daily in the Times ever since. Three days later The Daily Mail began to publish the puzzle under the name "Codenumber". The Daily Telegraph introduced its first Sudoku by its puzzle compiler Michael Mepham on 19 January 2005, and other Telegraph Group newspapers took it up very quickly. Nationwide News Pty Ltd began publishing the puzzle in The Daily Telegraph of Sydney on 20 May 2005; five puzzles with solutions were printed that day. The immense surge in popularity of Sudoku in British newspapers and internationally has led to it being dubbed in the world media in 2005 the "fastest growing puzzle in the world". It was not until the British Daily Telegraph introduced the puzzle on a daily basis on 23 February 2005 with the full front-page treatment advertising the fact, that the other UK national newspapers began to take real interest. The Telegraph continued to splash the puzzle on its front page, realizing that it was gaining sales simply by its presence. Until then the Times had kept very quiet about the huge daily interest that its daily Sudoku competition had aroused. That newspaper already had plans for taking advantage of their market lead, and a first Sudoku book was already on the stocks before any other national UK papers had realised just how popular Sudoku might be. By April and May 2005 the puzzle had become popular in these publications and it was rapidly introduced to several other national British newspapers including The Independent, The Guardian, The Sun (where it was labelled Sun Doku), and The Daily Mirror. As the name Sudoku became well-known in Britain, the Daily Mail adopted it in place of its earlier name "Codenumber". Newspapers competed to promote their Sudoku puzzles, with The Times and the Daily Mail each claiming to have been the first to feature Sudoku. The rapid rise of Sudoku from relative obscurity in Britain to a front-page feature in national newspapers attracted commentary in the media (see References below) and parody (such as when The Guardian's G2 section advertised itself as the first newspaper supplement with a Sudoku grid on every page [16]). Sudoku became particularly prominent in newspapers soon after the 2005 general election leading some commentators to suggest that it was filling the gaps previously occupied by election coverage. A simpler explanation is that the puzzle attracts and retains readers—Sudoku players report an increasing sense of satisfaction as a puzzle approaches completion. 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 included a daily Sudoku game in their Teletext service (at page 391). On 2 August 2005, the BBC's programme guide Radio Times started to feature a weekly Super Sudoku. The Dutch company Mobile Excellence International developed together with their Vietnamese partner the first mobile i-mode Sudoku game. The game was launched throughout Europe in September 2005. [17] The world's first live TV Sudoku show, 1 July 2005, Sky One. As a one-off, the world's first live TV Sudoku show, Sudoku Live, was broadcast on 1 July 2005 on Sky One. It was presented by Carol Vorderman. 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. Conferring was permitted although the lack of acquaintance of the players with each other inhibited an analytical discussion. The audience at home was in a separate interactive competition. A Sky One publicity stunt to promote the programme with the world's largest Sudoku puzzle went awry when the 275 foot (84 m) square puzzle was found to have 1,905 correct solutions. The puzzle was carved into a hillside in Chipping Sodbury, near Bristol, England, in view of the M4 motorway. The stunt was cleverly timed to coincide with a major road expansion, where an imposed 40 mph speed restriction allowed drivers to safely view the puzzle whilst driving. United States broadcaster CBS has run several stories concerning Sudoku, including on the Early Show in summer 2005, and on the CBS Evening News that autumn, on October 26. Dr. House was clearly seen working on a Sudoku puzzle on his office computer in one scene of the December 13, 2005 episode of House, M. D.; Sudoku is supposedly now banned on the studio set due to the cast constantly playing it. During February 7th's episode of The Daily Show, correspondent Jason Jones suggested that to ease the conflict over the Jyllands-Posten Muhammed caricatures, newspapers should be stripped down to only featuring Sudoku puzzles. There are also Sudoku video games, such as Go! Sudoku for the PSP "Dr. Sudoku" for the GBA and two sudoku games for the DS: "Sudoku Mania" and "Sudoku Gridmaster". Sudoku puzzles are also featured in Brain Age. See also List of newspapers featuring Sudoku List of Nikoli puzzle types List of Sudoku terms and jargon Latin square Killer Sudoku References ^ Garns, H. "Number Place." Dell Pencil Puzzles & Word Games. No. 16, May p. 6, 1979. sudoku.com Website of Wayne Gould, populariser of Sudoku; also includes forum which discusses solution techniques and mathematics of Sudoku NRC Sudokus - information about NRC Sudokus Sudoku Variations article at MAA Online; also includes the history of the puzzle's invention Basic Solving Techniques Keys to Solution at Puzzle Japan Solving Sudoku Step-by-step guide by Michael Mepham Mathematics of Sudoku Complexity and Completeness of Finding Another Solution and its Application to Puzzles Mathematical reference proving NP-completeness Frazer Jarvis's Sudoku page Contains programs, data, an article with Bertram Felgenhauer detailing the enumeration of Sudoku grids, and the results of Ed Russell Hayes, B., "Unwed Numbers - The mathematics of Sudoku, a puzzle that boasts 'No math required!'", American Scientist 94(1):12 (2006) [18]. History Rules and history from the Nikoli website Boyer, C., « Les ancêtres français du sudoku », Pour La Science 344 (June 2006), pages 8-11 & 89 Article in The Times on Sudoku's alleged French ancestry Java Programs to Solve Sudokus Solving Sudokus in Java An article explaining how to solve Sudokus using Constraint programming in Java by Koalog Java Sudoku Solver A short program to solve Sudoku problems using backtracking similar to the eight-queens algorithm. Commentary on the sudden popularity of Sudoku in Britain: The puzzling popularity of Su Doku (BBC News, 22 April 2005) So you thought Sudoku came from the Land of the Rising Sun… (The Observer, 15 May 2005) Do you sudoku? (The Economist, 19 May 2005) External links This article or section may contain external links added only to promote a website, product, or service – otherwise known as spam. If you are familiar with the content of the external links, please help by removing commercial links, in accordance with Wikipedia:External links. (you can help!) Sudoku at the Open Directory Project – An active listing of Sudoku links. Sudoku Programmers Forum     Search Term: "Sudoku" Categories: Wikipedia spam cleanup | 2000s fads | English words of foreign origin | Puzzle computer and video games | Sudoku

Million-puzzle 'Sudoku' offers martial-arts kick