Advanced | Help | Encyclopedia
Directory

• Encyclopaedia
• S
• Su
• Sua
• Sub
• Suc
• Sud
• Sue
• Suf
• Sug
• Suh
• Sui
• Suj
• Suk
• Sul
• Sum
• Sun
• Suo
• Sup
• Suq
• Sur
• Sus
• Sut
• Suu
• Suv
• Suw
• Sux
• Suy
• Suz

Sudoku

(Redirected from Su Doku)
Difficult Sudoku puzzle

Sudoku is a number placement puzzle, also known as Number Place in the United States. Completing the puzzle requires only patience and modest logical ability (although some puzzles can be fiendish). Its classic grid layout is reminiscent of other popular newspaper puzzles such as crosswords and chess. Sudoku is recommended by some teachers as a mental exercise.

Table of contents

History and terminology

The puzzle seems to have first been published in New York in the late 1970s by the specialist puzzle publisher Dell, which refers to it as Number Place. The person who devised the first puzzle is not recorded. The description "number place" is somewhat misleading as there is nothing unique about the choice of numbers: the puzzle would still work if each specific number were to be substituted by another specific number (like swapping all the 8s and 4s, etc.) or to be replaced by an arbitrary non-numerical image. Indeed, Penny Press uses letters in their version called Scramblets.

In the 1980s the ouzzle was popularised in Japan by Nikoli, which created the Sudoku name. The name is Japanese; in kanji it is written 数独, which implies "multiple isolations". The Japanese writing system is unsuitable for crosswords thus leaving a gap in the market for for number and logic puzzles. Wayne Gould, a New Zealander and former High Court Judge of Hong Kong, discovered the puzzle in Japan and promoted the idea to The Times launching it on 12 November 2004; three days later the Daily Mail began to publish the puzzle under the name "Codenumber" (it has since been renamed Sudoku). By April of 2005 it was becoming immensely popular in the United Kingdom, and has now been adopted by several other national British newspapers including (The Daily Telegraph, The Independent, The Guardian, The Sun and The Daily Mirror) and the international press is following suit. Bringing the process full-circle, the New York Post is publishing the puzzle and the Kappa reprints Nikoli Sudoku in GAMES Magazine under the name Squared Away. It is also often included in puzzle anthologies, such as The Giant 1001 Puzzle Book (under the title Nine Numbers).

The challenge

The puzzle is played on a grid, most frequently a 9×9 grid made up of 3×3 subgrids (called "regions") and starting with various numbers in the range of 1 through 9 given in some cells (the "givens"). The goal is to fill in the empty cells, one number in each, so that every column, row, and region each contains the numbers 1 through 9 once. Therefore, each number in the solution is unique – or alone – in each of three "directions", hence "multiple isolations". The attraction of the puzzle is that the completion rules are so simple, yet the overall task can be difficult. Each puzzle can be ranked in terms of difficulty depending upon how many numbers are given and how easy it is to logically determine subsequent numbers once the puzzle has been started.

Solution methods

The 3×3 region in the top-left corner must contain a 7. But where? By hatching across and up from 7s located elsewhere in the grid, we can eliminate all of the empty squares in the top-left corner which cannot contain 7. This leaves only one possible square. (It is highlighted in green.)

There are several strategies involving a combination of the following techniques. The first two techniques are performed at the outset and periodically throughout the solution process.

  • Cross-hatching, being the reading of rows (or columns) to identify firstly which three square line must have a certain number, and secondly, reading down the columns (or rows), discovering which of these squares must contain the number. Typically the number tested would be one which appears frequently in the initial puzzle.
  • Counting 1–9 in regions, rows, and columns. Counting based upon the last number discovered may speed up the search.
  • Marking candidate numbers in blank squares. There are two popular notations. One is to write in the possible numbers in subscript in the squares. The other is to use 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. Once a complete set of candidate numbers has been written out then a process of elimination soon arrives at an answer.
  • Peforming a what-if on squares with only two candidate numbers. Then repeat the steps as above until a duplication is found, in which case choose the alternative candidate number. This particular option requires a pencil and eraser. This approach may be frowned on by logical purists as too much trial and error 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 squares can be time-consuming. The what-if approach can be confusing unless you are well organised. The Holy Grail is to find a technique which minimises counting, marking up, and rubbing out.

Computer solutions

For computer programmers it is relatively simple to build a brute force search. Typically this would assign a value (say, 1, or the nearest available number to 1) to the first available square (say, the top left hand corner) and then move on to assign the next available value (say, 2) to the next available square. This continues until a duplication is discovered in which case the next alternative value is placed in the last field changed. This isn't remotely computationally efficient, but it will work. 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. This more closely emulates the way a human would solve the puzzle without resorting to trial and error, but coding the search for impossibilities based on contingencies and even multiple contingencies (as would be required for the hardest of Sudoku) is a daunting task.

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 even be deduced from other givens. They also have no authoring credits. 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 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 states that its puzzles are hand-constructed "in Japan", though it does not include authoring credits.

Note that 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 torturous that logic may be – can result in an unsolvable puzzle when defining a future given contradicts what has already been built.

Variants

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

Mathematics of Sudoku

Sudoku puzzles are known to be NP-complete [1].

Mathematicians would say that solving Sudoku puzzles in general is essentially a problem in graph coloring. The aim of the puzzle in its standard form is to construct a proper 9-coloring of a particular graph, given a partial 9-coloring. The graph in question has 81 vertices, one vertex for each square of the grid. The vertices can be labelled with the ordered pairs <math>(x,\, y)<math>, where x and y are integers between 1 and 9. In this case, the vertices labelled by <math>(x,\, y)<math> and <math>(x',\, y')<math> are joined by an edge if and only if:

  • x = x' or,
  • y = y' or,
  • <math> x \equiv x' \pmod{3} <math> and <math> y \equiv y' \pmod{3} <math>.

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. The matching involved is related in principle to Hall's marriage theorem, in that the inductive method to prove Hall's theorem throws light on deductions to be made from any given set of restricted possibilities.

There is an obvious similarity to these puzzles and Latin squares, the solved grids necessarily being Latin squares with the additional regional restriction – hence one of its published names, Quadrum Quandary, being rather punny ('quadrum' is Latin for 'square'). Although the quantity of Latin squares for many given sizes is known, including 9×9, the number of valid Sudoku solution grids for even the standard 9×9 grid with 3×3 regions is apparently unknown; members of the Dell forum are presently working on the problem.

See also

External links







Links: Addme | Keyword Research | Paid Inclusion | Femail | Software | Completive Intelligence

Add URL | About Slider | FREE Slider Toolbar - Simply Amazing
Copyright © 2000-2008 Slider.com. All rights reserved.
Content is distributed under the GNU Free Documentation License.