Sudoku Solver

Sudoku is essentially a pattern matching game. In a properly solved game, each row will use all of the numbers 1-9, each column will use all of the numbers 1-9 and each 3 x 3 subtable will use the numbers 1-9.

The Solution

In order to solve a puzzle, you essentially do the following:

• Find a cell that already has a value. From this, you know that every other cell in this cell's row, column and 3 x 3 table can not have this value. Denote what cells cannot hold what numbers.
  
  
• Identify Must Be's from the pattern. For example, look at the following table:
  
  

  In this table, you can see from the red and yellow lines where the empty cells cannot hold a 5. Since each 3 x 3 table must contain each number 1-9 as well, this means that the blue colored cell must be a 5. This process is sometimes referred to as cross-hatching.

• Repeat the first two steps as long as new pieces of the puzzle continue to be revealed. For most puzzles, the whole puzzle can be completed using these steps. In very difficult puzzles, you will reach a point where you would need to guess a value for a given cell. From there, you complete the puzzle using steps 1 and 2 again, etc. When you guess, however, you should be prepared to back up to the point of the guess in case you are incorrect.

The Computer Solution

My computer program essentially uses guessing and iteration to solve the problem. Historically, I used the exact solution mechanism proposed above. However, the time required for the computer to solve the program that way vs. guessing was not appreciably different, so this way has a smaller, cleaner code base.