Pssst... Would you rather
play Online Chess against the computer while reading the latest news?
It takes some time to load the necessary javascript, so just wait till the chess board comes up.


About Sudoku

From Wikipedia, the free encyclopedia.

A Sudoku puzzle, sometimes spelled Su Doku, is a logic-based placement puzzle, also known as Number Place in the United States. The aim of the canonical puzzle is to enter a numeral from 1 through 9 in each cell of a 9x9 grid made up of 3x3 subgrids (called "regions"), starting with various numerals given in some cells (the "givens"). Each row, column and region must contain only one instance of each numeral.

Completing the puzzle requires patience and logical ability. Its grid layout is reminiscent of other newspaper puzzles like crosswords and chess problems. Although first published in 1979, Sudoku initially became popular in Japan in 1986 and attained international popularity in 2005.

Introduction

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

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

Rules and terminology

The puzzle is most frequently a 9x9 grid made up of 3x3 subgrids (called "regions"). Some cells already contain numbers, known as "givens". The goal is to fill in the empty cells, one number in each, so that each column, row, and region contains the numbers 19 exactly once. Each number in the solution therefore occurs only once in each of three "directions", hence the "single numbers" implied by the puzzle's name.

Solution methods

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

Scanning

Scanning is performed at the outset and periodically throughout the solution. Scans may have to be performed several times in between analysis periods. Two basic techniques comprise scanning: Cross-hatching: the scanning of rows (or columns) to identify which line in a particular region may contain a certain number by a process of elimination. This process is then repeated with the columns (or rows). For fastest results, the numbers are scanned in order of their frequency. It is important to perform this process systematically, checking all of the digits 19. Counting 19 in regions, rows, and columns to identify missing numbers. Counting based upon the last number discovered may speed up the search. It also can be the case (typically in tougher puzzles) that the value of an individual cell can be determined by counting in reverse that is, scanning its region, row, and column for values it cannot be to see which is left. Advanced solvers look for "contingencies" while scanning that is, narrowing a number'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 which 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.

Marking up

Scanning comes to a halt when no further numbers 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 numbers in the blank cells. There are two popular notations: subscripts and dots.

In the subscript notation the candidate numbers 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 is a pattern of dots with a dot in the top left hand corner representing a 1 and a dot in the bottom right hand corner representing a 9. 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 pencil would then be recommended.

Analysing

Two main analysis approaches are "elimination" and "what-if".

In elimination, progress is made by successively eliminating candidate numbers 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 latest number. There are a number of elimination tactics, all of which are based on the simple rules given above, which have important and useful corollaries, including: 1. A given set of n cells in any particular block, row, or column can only accommodate n different numbers. This is the basis for the "unmatched candidate deletion" technique, discussed below. 2. Each set of candidate numbers, 1-9, must ultimately be in an independently self-consistent pattern. This is the basis for advanced analysis techniques that require inspection of the entire set of possibilities for a given candidate number. Only certain "closed circuit" or "nxn grid" possibilities exist (which have acquired peculiar names such as "X-wing" and "Swordfish", among others). If these patterns can be identified, elimination of candidate possibilities external to the grid framework can sometimes be achieved. One of the most common elimination tactics is "unmatched candidate deletion". Cells with identical sets of candidate numbers are said to be matched if the quantity of candidate numbers in each is equal to the number of cells containing them. For example, cells are said to be matched within a particular row, column, or region (scope) if two cells contain the same pair of candidate numbers (p,q) and no others, or if three cells contain the same triplet of candidate numbers (p,q,r) and no others. These are essential coincident contingencies; the placement of these numbers anywhere else in the matching scope would make a solution for the matched cells impossible. Thus, the candidate numbers (p,q,r) appearing in unmatched cells in the row, column or region scope can be deleted. This principle also works with candidate number subsets -- if three cells only have candidates (p,q,r), (p,q) and (q,r), or even (p,r), (q,r) and (p,q), all of the set (p,q,r) elsewhere in the scope can be deleted. The principle is true for all quantities of candidate numbers. A second related principle is also true -- if the number of cells (in a row, column or region scope) where a set of candidate numbers only appear is equal to the quantity of candidate numbers, the cells and numbers are matched and only those numbers can appear in matched cells. Other candidates in the matched cells can be eliminated. For example, if (p,q) can only appear in 2 cells (within a specific row, column, region scope), other candidates in the 2 cells can be eliminated. The first principle is based on cells where only matched numbers appear. The second is based on numbers that appear only in matched cells. Advanced techniques carry these concepts further to include multiple rows, columns, and blocks. (See "X-wing" and "Swordfish", above.) In the what-if approach, a cell with only two candidate numbers 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 is the solution. In logical terms, this is known as reductio ad absurdum. Nishio is a limited form of this approach: for each candidate for a cell, the question is posed: will entering a particular number prevent completion of the other placements of that number? 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 will never be necessary to resort to this tactic,) but it can arrive at solutions fairly rapidly. Ideally one needs to find a combination of techniques which avoids some of the drawbacks of the above elements. The counting of regions, rows, and columns can feel boring. Writing candidate numbers 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 which minimises counting, marking up, and rubbing out.

Computer solutions

For computer programmers, coding the search for cell values based elimination, contingencies and multiple contingencies ( required for harder Sudoku) is relatively straightforward. These programs emulate the human logic to solve a puzzle without resorting to guesses. Given the self-imposed constraints of most Sudoku publishers, this method generally succeeds.

It is also fairly simple to build a backtracking search. Typically this involves assigning a value (say, 1, or the nearest available number to 1) to the first available cell (say, the top left hand corner) and then moves on to assign the next available value (say, 2) to the next available cell. This continues until a conflict occurs, in which case the next alternative value is used for the last cell changed. If a cell cannot be filled, the program backs up one level (from that cell) and tries the next value at the higher level (hence the name backtracking). Although far from computationally efficient, this method will find a solution, given sufficient computation time. A standard 9x9 puzzle can typically be "solved" within one or two seconds on a modern home computer running this algorithm in an interpreted language, such as Perl, and much less in a compiled language. A more efficient program could keep track of potential values for cells, eliminating impossible values until only one value remains for a cell, then filling that cell in and using that information for more eliminations, and so on until the puzzle is solved.

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 3x3 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.

A highly efficient way of solving such constraint problems is the Dancing Links Algorithm, by Donald Knuth. This method can be directly applied to solving Sudoku problems, counting all possible solutions for most puzzles in milliseconds. This is the method now preferred by many Sudoku programmers, mainly by virtue of its speed. A very fast solver is usually required for most trial-and-error puzzle-creation algorithms.

Difficulty ratings

Published puzzles often are ranked in terms of difficulty. The difficulty of the puzzle depends upon how easy it is to logically determine subsequent numbers. Perhaps surprisingly, the number of givens has little or no bearing on a puzzle's difficulty. Puzzles with a minimum number of givens can be very easy to solve, and puzzles with more than the average number of givens can still be extremely difficult to solve.

Computer solvers can estimate the difficulty for a human to find the solution, based on the complexity of the rules required by the computer. This estimation is usually accurate, allowing publishers to rate their Sudoku puzzles for the right type of audience. Some online versions offer several difficulty levels.

There are many factors that influence the difficulty of a Sudoku puzzle. A standard formula takes into account four ratings:

Rating of fillable squares. Rating of squares found using the process of elimination. Rating of guesses that had to be done to reach the solution. Rating of backtraces performed in order to solve the puzzle. The first two ratings are negative: the higher they are, the lower the difficulty will be. The last two ratings are positive, and they increase the puzzle difficulty.

Construction

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

Nikoli Sudoku are hand-constructed, with the author being credited beside each puzzle; the givens are always found in a symmetrical pattern. (Building a Sudoku with symmetrical givens can be achieved by determining in advance where the givens will be located, and only assigning an actual number to them as needed.) Dell Number Place Challenger (see Variants below) puzzles also list author credits. The Sudoku puzzles printed in most UK newspapers are apparently computer-generated but employ symmetrical givens, implying a more humanistic algorithm; The Guardian claims its puzzles are hand-constructed "in Japan" (they are, in fact, created by the first Japanese Sudoku setters at Nikoli) though it does not include authoring credits. The Guardian famously claimed that because they were hand-constructed, their puzzles would contain "imperceptible witticisms" that would be very unlikely in computer-generated sudoku.

It is possible to set starting grids with more than one solution and to set grids with no solution, but such are not considered proper Sudoku puzzles; like most other pure-logic puzzles, a unique solution is expected. Great caution is required in constructing a Sudoku puzzle, 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.

If an efficient solver is available, there is a very simple method of automatic construction: randomly add a digit to the grid, and then look for a solution. If no solution is found, remove the digit and try another. If a solution is found, look for a different solution. If there is no other solution, the starting grid is complete; otherwise, repeat this process.

History

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

Popularity in the media

In 1997, retired Hong Kong judge Wayne Gould, 59, a New Zealander, was enticed by seeing a partly completed puzzle in a Japanese bookshop. He went on to develop a computer program to produce puzzles quickly; this took over six years. 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. 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 variously as "the Rubik's cube of the 21st century" or the "fastest growing puzzle in the world"

There is no doubt that it was not until The 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 of the other national 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, and The Guardian claiming (though perhaps ironically) that its hand-made puzzles, licensed from Nikoli, offered a superior experience (complete with "almost imperceptible witticisms") to the computer-generated grids found in other papers.

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 [13]). 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 142).

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.


This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Sudoku".

Oh well.... If you really want to:
Here's the link to Sudoku Online Puzzle
Just remember that it can be a very addictive game!


Going somewhere today and afraid you'll be bored to death?
Just print several puzzles
to take along. Four puzzles fit on a sheet of paper including the right solution.