Hi,
i wants to increase my creativity and inovation power.I think that this is one of the best way to make your mind upto date, through puzzels.

Variants

Although the 9x9 grid with 3x3 regions is by far the most common, numerous variations abound: sample puzzles can be 4x4 grids with 2x2 regions; 5x5 grids with pentomino regions have been published under the name Logi-5; the World Puzzle Championship has previously featured a 6x6 grid with 2x3 regions and a 7x7 grid with six heptomino regions and a disjoint region. Even the 9x9 grid is not always standard, with Ebb regularly publishing some of those with nonomino regions. Larger grids are also possible, with Dell regularly publishing 16x16-grid Number Place Challenger puzzles and Nikoli proffering 25x25 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.

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

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

Alphabetical variations, which use letters rather than numbers, have also emerged. The Guardian calls these Godoku and describes them as .devilish'. Others title them Wordoku. The required letters are given beneath the puzzle. Once arranged they spell out a topical word between the top left and bottom right corners. This adds an extra dimension to Sudoku as it may be possible to guess what the word is, indicating what some of the unfilled cells might be.

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

• Sequentially connected puzzles: several standard 9x9 puzzles are solved consecutively. Only the first puzzle has enough givens to be solved on its own; once the first puzzle is solved, one or more numbers are transferred from its solution to the starting grid of the second, etc. In some cases, the solver must work back and forth between partially completed puzzles.
• Very large puzzles made up of multiple overlapping puzzles (usually, but not always, 9x9s). Puzzles made up of 20 to 50 or more standard grids are not uncommon. The region of overlap varies x two 9x9s may share 9, 18, or 36 cells. Often, there are no givens in overlapped areas.
• Otherwise standard puzzles in which each cell is a member of four groups rather than the normal three (rows, columns, and regions): digits with the same relative location within their respective regions must not match. Such puzzles are usually printed in colour, with each disjoint group sharing one colour for clarity.
  The 2005 U.S. qualifier for the World Puzzle Championship includes a variant called Digital Number Place: rather than givens, most cells contain a partial given - a segment of a number, with the numbers drawn as if part of a liquid crystal display.

Wikipedia, the free encyclopedia.

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. Scanning comprises two basic techniques, cross-hatching and counting, which may be used alternately:

• 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 1-9.
• Counting 1-9 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.

Analysing

There are two main analysis approaches - 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. One of the most common 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 if two cells contain the same pair of candidate numbers (p,q) and no others, or if three cells contain the same triple of candidate numbers (p,q,r) and no others. These are essentially coincident contingencies. These numbers (p,q,r) appearing as candidates elsewhere in the same row, column, or region in unmatched cells can be deleted.
• 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, 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 if 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 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 cells 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.

Wikipedia, the free encyclopedia.

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 1 through 9 exactly once. Each number in the solution therefore occurs only once in each of three "directions", hence the "single numbers" implied by the puzzle's name.

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. Published puzzles often are ranked in terms of difficulty. This also may be expressed by giving an estimated solution time. While, generally speaking, the greater the number of givens, the easier the solution, the opposite is not necessarily true. The true difficulty of the puzzle depends upon how easy it is to logically determine subsequent numbers.

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 class. The puzzles are often available free from published sources and also may be custom-generated using software.

Wikipedia, the free encyclopedia.

Mathematics of Sudoku

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

However, for a non-trivial starting board, the game tree is very large and so this method is not feasible. The problem of solving a puzzle that is known to have only one solution is in UP.

Solving Sudoku puzzles can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labelled with the ordered pairs , 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 valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9x9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960, which is roughly the number of micrometers to the nearest star. This number is equivalent to 9! x 72^2 x 2^7 x 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. A paper detailing the methodology of their analysis can be found at. The number of valid Sudoku solution grids for the 16x16 derivation is not known.

Of course, some of the 9x9 grids can easily be transformed into others; by relabelling the numbers, by rotating or reflecting the grid, and by permuting certain rows and columns. Ed Russell and Frazer Jarvis have counted the number of "essentially different" sudoku grids as 5,472,730,538: see the previous link for more details of the calculation.

Paul Muljadi discovers magic Sudoku, a Sudoku which contains at least one 3x3 normal magic square anywhere in the solution grid. Ed Russell creates 64 possible arrangements of magic Sudoku of five normal 3x3 magic squares in each.

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

Wikipedia, the free encyclopedia.

History

The puzzle was first published in New York in the late 1970s by the specialist puzzle publisher Dell Magazines in its magazine Math Puzzles and Logic Problems, under the title Number Place. The person who designed the puzzle and composed the first of its kind is not recorded, but it was probably Walter Mackey, one of Dell's puzzle constructors. The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as 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 Kaji Maki (鍜治 真起), the president of Nikoli. At a later date, the name was abbreviated to Sudoku (数独, pronounced SUE-dough-coo; 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. Nikoli still holds the trademark for the name Sudoku; other publications (at least in Japan) use other names.

Sudoku (Japanese: 数独,, sūdoku), sometimes spelled Su Doku, is a placement puzzle, also known as Number Place in the United States. The aim of the puzzle is to enter a number from 1 through 9 in each cell of a grid, most frequently a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various numbers given in some cells (the "givens"). Each row, column and region must contain only one instance of each number. Completing the puzzle requires patience and modest logical ability (although some puzzles can be very difficult). Its classic grid layout is reminiscent of other newspaper puzzles like crosswords and chess problems. First published in the United States, Sudoku initially became popular in Japan in 1986 and attained international popularity in 2005.

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. 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 in Visual C++, and although 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 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 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. Otherwise, look for a different solution. If there is no other solution, accept the current digit; otherwise, repeat this process.

Wikipedia, the free encyclopedia.

Computer solutions

For computer programmers it is relatively simple to build a backtracking search. Typically this would assign a value (say, 1, or the nearest available number to 1) to the first available cell (say, the top left hand corner) and then move on to assign the next available value (say, 2) to the next available cell. This continues until a duplication is discovered in which case the next alternative value is placed in the last field changed. Although far from computationally efficient, this method will find the solution, given sufficient computation time. 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 guesses.

Coding the search for impossibilities based on contingencies and even multiple contingencies (as would be required for the hardest of Sudoku) is quite complex to construct by hand. However, such complications are unnecessary if all the programmer wishes to do is find a solution efficiently. A more efficient way to find solutions involves the use of finite domain constraint programming. A constraint program requires the programmer only to specify the constraints on the solution (the fact that every number in each row, each column, and each 3x3 subgrid must be unique, and the provided "givens"); the finite domain solver does all the work of propagating additional information about possible values to narrow down the solution space until a unique solution is found. The self-imposed constraints of most Sudoku puzzle publishers even ensures that the backtracking search capabilities of the finite domain solver are not required.

Elaborate, hand-crafted solvers have been designed that apply scanning and marking up in a manner similar to human solvers. This allows these solvers to estimate the difficulty for a human to find the solution, based on the complexity of the rules required by the computer.

Difficulty ratings

Published puzzles often are ranked in terms of difficulty. Surprisingly, the number of givens has little or no bearing on a puzzle's difficulty. A puzzle with a minimum number of givens may be very easy to solve, and a puzzle with more than the average number of givens can still be extremely difficult to solve. It is based on the relevance and the positioning of the numbers rather than the quantity of the numbers.

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.

Wikipedia, the free encyclopedia.