Submitted by : -
Vaibhav Kumar Tripathi

---

[attachment=12480]
Introduction
C was one of the first general-purpose high-level programming languages to gain almost universal use, and today you can program in C on almost any platform and machine. It was created by Dennis Ritchie in 1971, as the successor to the "B" compiler, for UNIX systems.
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 (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. Completed puzzles are usually a type of Latin square with an additional constraint on the contents of individual regions . Sudoku was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number.It became an international hit in 2005.Sudoku was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It became an international hit in 2005.
Histroy
Number puzzles first 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 diagonals 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 the First World War.
According to Will Shortz, the modern Sudoku was most likely designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor from Indiana, and first published in 1979 by Dell Magazines as Number Place (the earliest known examples of modern Sudoku). Garns's 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 in the paper Monthly Nikolist in April 1984 asSuuji (or suji) wa dokushin ni kagiru , which can be translated as "the digits must be single" or "the digits are limited to one occurrence." At a later date, the name was abbreviated to Sudoku by Maki Kaji, taking only the first kanji 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). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun.
Mathematics of sudoku
A completed Sudoku grid is a special type of Latin square 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 newsgroup rec.puzzles in September 2003 and is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS). This is roughly 1.2×10−6 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 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 (sequence A109741 in OEIS).
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, 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.
Recent popularity
Sudoku software is very popular on PCs, websites, and mobile phones. It comes with many distributions of Linux. Software has also been released on video game consoles, such as the Nintendo DS, PlayStation Portable, the Game Boy Advance, Xbox Live Arcade, several iPod models, and the iPhone. 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!. Critically and commercially well received, it generated particular praise for its Sudoku implementationand 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 Australian drugs-related jury trial costing over AU$1 000 000 was aborted when it was discovered that five of the twelve jurors had been playing Sudoku instead of listening to evidence.
List organization and conventions
This list provides a brief glossary of Sudoku terminology. Items are listed thematically, and usually only once, with a brief description and possibly a page link to a detailed description. Links to example usage are provided as in-line numbered references . Here the default usage of Sudoku refers to the prominent 9×9 format, as illustrated.
Grid layout and puzzle terms
A Sudokugrid has 9 rows, columns and boxes each having 9 cells. The full grid has 81 cells. Cells are commonly called squares, but in technical descriptions the term square is avoided since the boxes and grid are also squares. Boxes are also known as blocks or zones. Three vertically stacked blocks make a stack. Three horizontally connected blocks make a band. A chute is either a band or a stack. A grid has 3 bands, 3 stacks and 6 chutes.
The use of the boxes to partition the grid can be generalized to other equal sized partition shapes, in which case the sub-areas are known as regions, zones, subgrids, or nonets. See Variants below. In some cases the regions are only equal sized, not equal shaped.
Rows, columns and regions are collectively referred to as units or scopes, of which the grid has 27. The One Rule can then be compactly stated as: 'Each digit appears once in each unit'.
Size refers to the size of a puzzle or grid. Often a composite row × column designation is used, e.g. size 9×9. In technical discussions size may mean the number of cells, e.g. 81. Since the number of cells in a region must be the side dimension of the square grid, e.g. 9 cells per block for a 9×9 grid, it is convenient to just use the region size, e.g. 9.
Puzzle terms
A puzzle is a partially completed grid. The initially defined values are known as givens or clues. A proper puzzle has a single (unique) solution. A proper puzzle that can be solved without trial and error (guessing) is known as a satisfactory puzzle. An irreducible puzzle (a.k.a. minimum puzzle) is a proper puzzle from which no givens can be removed leaving it a proper puzzle (with a single solution). It is possible to construct minimum puzzles with different number of givens. The minimum number of givens refers to the minimum over all proper puzzles and identifies a subset of minimum puzzles. See Mathematics of Sudoku-Minimum number of givens for values and details.
Sudoku variants
The classic 9×9 Sudoku format can be generalized to an
N×N row-column grid partitioned into N regions, where each of the N rows, columns and regions have N cells and each of the N digits occur once in each row, column or region.
This accommodates variants by region size and shape, e.g. 6 cell rectangular regions (The N×NSudoku grid is always square). For prime N, polyominos shaped regions can be used. The requirement to use equal sized regions, or have the regions cover the grid entirely can also be relaxed.
Other variation types include additional value placement constraints, alternate cell symbols (e.g. letters), alternate mechanism for expressing the clues, and composition with overlapping grids. This page provides a simple list of variants. See Sudoku - Variants for details and additional variants.
For rectangular regions the row-column dimensions of the region may be used to describe the grid as whole, e.g. 3×2, since each of the grid side dimensions must be the product of row *column, e.g. for a 3×2 rectangular region, the grid must be 6×6. For rectangles of size N×1 or 1×N, the region is a row or column, and Sudoku becomes a Latin square.
Sudoku types and classes
Sub Doku
Grids smaller than 9×9.Sometimes referred to as Children's Sudoku (especially the 4×4 variant) as the reduced number of possibilities makes them easier to solve.
Super Doku
Grids larger than 9×9.
Prime Doku
N×N grid where N is prime. Generally constructed with polyomino regions, e.g. Go Doku and pentominos.
Maximum Su Doku
The class of puzzles which have the maximum number of independent clues needed to allow a complete and unique solution.
Minimum Su Doku
The class of puzzles which have the minimum number of clues needed to allow a complete and unique solution.
Proper puzzle
A puzzle that has a unique solution.
Satisfactory puzzle
A puzzle that does not require trial and error. Note: the level of trial and error is usually not explicitly defined, see trial and error below.
Purely numeric puzzle
Puzzles which use purely numbers.
Purely literal puzzle
A sudoku puzzle which uses letters instead of numbers.
Numeroliteral puzzle
Puzzles using a combination of letters and numbers, usually seen in 12x12 sudoku puzzles.
Variants by size
Polyomino
A shape composed of equal sized, side-adjacent squares. Often used for Sudoku region variants. Polyominos are named by size: (5)pentomino, (6)hexomino, (7)heptomino, (8)octomino, and (9)nonomino.
Du-sum-oh
5×5, 6×6, 7×7, 8×8 or 9×9 grid with irregular, polyomino, shaped regions and minimal number of clues.
Du-Sum-Oh puzzles are also known as Latin Squares Puzzles (invented by Mark Thompson), Squiggly Sudoku, Jigsaw Sudoku, Irregular Sudoku, or Geometric Sudoku. These puzzles typically have anywhere from 5 to 9 rows. The number of rows is always equal to the number of columns. The regions are polyominos made of the same number of squares that are in any one row of the puzzle. The irregularity of the regions compensates for the relatively small number of givens.
4×4
Shi Doku
Four 2×2 regions.Shi is Japanese for 4.
5×5
Go Doku
5×5 grid with pentomino regions.Go is Japanese for 5.
Logi-5
5×5 grid with pentomino regions
6×6
These use 6 2×3 rectangular regions:
Roku Doku
(unnamed)
featured at the World Puzzle Championship
Sudoku X - with unique main diagonals
7×7
(unnamed)
7×7 grid with six heptomino regions and a disjoint region, featured at the World Puzzle Championship.
8×8
Super Sudoku X - 4 4×2 + 4 2×4 rectangular blocks.
9×9
Sudoku
Classic 9×9 grid with nine 3×3 regions.
Jigsaw Sudoku
9×9 grid with nonomino regions.
Du-sum-oh
5×5, 6×6, 7×7, 8×8 or 9×9 grid with irregular, polyomino, shaped regions and minimal number of clues.
Only 'One Rule' variant puzzles with simple givens are listed in this section. For variants with other clue mechanisms, see Constraint and clue variants.
12×12
Maxi
twelve 3×4 rectangular blocks.
16×16
Number Place Challenger
Sixteen 4×4 regions.