SUDOKUbboard

Sudoku

Sudoku (??, s?doku), also known as Number Place or Nanpure, is a logic-based placement puzzle. Originally from Japan, the name "Sudoku" is the Japanese abbreviation of a longer phrase, "Suuji wa dokushin ni kagiru" (????????, "Suuji wa dokushin ni kagiru"), meaning, "the digits must remain single." It became popular in the US and Europe recently after The Times in London began publishing a weekly Sudoku puzzle in 2004.

The aim of the puzzle is to enter a number from 1 through 9 in each cell of a 99 grid made up of 33 subgrids (called "regions"), starting with various digits given in some cells (the "givens"); each row, column, and region must contain only one instance of each numeral, 1 through 9.

Techniques

Scanning

Scanning at the outset and between analyses can be a very quick way to solve pieces of the total puzzle. Scanning consists of two techniques:

- Cross-hatching: the scanning of rows to identify which line in a region may contain a certain numeral by a process of elimination. You repeat the process with the columns. For fastest results, scan the numbers in order of their frequency. It is important to perform this process systematically, checking all of the digits 1-9.

The 33 region in the top-right corner must contain a 5. By hatching across and up from 5s located elsewhere in the grid, you can eliminate all the empty cells in the top-right corner which cannot contain a 5. This leaves only one possible cell for a 5 (highlighted in green).

- Counting 1-9 in regions, rows, and columns to identify missing numerals. Counting based upon the last numeral discovered may speed up the search. It also can be the case, particularly in tougher puzzles, that the best way to ascertain the value of a cell is to count in reverse-that is, by scanning the cell's region, row, and column for values it cannot be, in order to see what remains.

Marking up

Scanning stops when you cannot discover any further numbers, making it necessary to engage in logical analysis. One method to guide the analysis is to mark candidate numerals in the blank cells. There are two popular notations: subscripts and dots.

- In the subscript notation, you write the candidate numerals in subscript, or very small writing, in the cells. However, original puzzles printed in a newspaper usually are too small to accommodate more than a few digits of normal handwriting. Thus, solvers often create a larger copy of the puzzle.

- The second notation uses a pattern of dots in each square, where the dot position indicates a number from 1 to 9. You can use the dot notation on the original puzzle.

This is a method for marking likely numerals in a single cell by the placing of pencil dots. To reduce the number of dots used in each cell, you would only mark dots after adding as many numbers as possible to the puzzle by scanning. You then erase dots as you eliminate their corresponding numerals as candidates.

- An alternative technique is to "mark up" the numerals that a cell cannot be. A cell will start empty and as you eliminate possibilities, it will slowly fill until only one mark is missing.

Candidate elimination

In "candidate elimination," you successively eliminate potential numbers from cells until only one number is possible in a given cell. After each answer, you do another scan-usually checking to see the effect of that new number on the other parts of the puzzle. One method works by identifying "matched cells."

If precisely two cells within a scope (a particular row, column, or region) contain the same two potential numerals (p,q), or if precisely three cells within a scope contain the same three potential numerals (p,q,r), these cells are said to be matched. The placement of these numerals anywhere else within that same scope would make a solution impossible; thus, you can delete those numerals (p,q,r) as potential numerals in other cells. If, for example, two cells are either p or q, then you can eliminate p and q from a third cell. You do not know which cell is p or which is q yet, but you know they cannot occur elsewhere in that scope. When all else fails, ask the question, 'Would entering this number prevent completion of the other necessary placements?' If the answer is 'Yes,' then eliminate the number in question.

The "What-If" Approach

In the "what-if" approach, you make a guess about the solution to a cell with two potential numerals. As you continue the puzzle, if a cell is left without a possible candidate or the only solution to another cell is a duplicate number, the alternative candidate must be the solution to that first cell and you have to backtrack. The what-if approach requires a pencil and eraser or a good layout memory.

***Info from http://en.wikipedia.com