- Online Games
- Guest posts
Submitted by nishank on Tue, 2006-05-09 09:46.
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.
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.
The 3x3 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-left corner which cannot contain a 5. This leaves only one possible cell (highlighted in green).
The strategy for solving a puzzle may be regarded as comprising a combination of three processes: scanning, marking up, and analysing.
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.
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.
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.
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.
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.
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.