SUDOKU

Introduction

The sudoku puzzle is made up of a square containing 9x9 cells. The square itself is subdivided into 9-3x3 sub-squares. The object of the game is to provide one digit numbers (1-9) into the cells such that each row, each column, and each subsquare contain the nine distinct digits. A number of cells are prefilled to ensure that the solution is unique.
A well-made sudoku game will have a unique solution, and which can be solved by logical deductions without trial and error. The extremely difficult ones involve a one-level trial and error, but mostly reasoning.

How do we solve the puzzle

It is relatively easy, probably easier than crossword puzzles. You do not need to be a vocabulary expert to master it, and it works in any language.
1. Choose an empty cell and enumerate all the numbers in the row and the column that criss-cross the cell. Include also the numbers contained in the same subsquare as the empty cell. Do not count doubles. If you come up with 1,2,4,5,6,8,9, then you deduce that the missing 3 and 7 are possible candidates for this square. Write down in pencil 3 and 7 near the bottom of the cell.
2. Repeat step 1 until you find a cell that has only one possible candidate. THIS IS YOUR ANSWER for that cell. When a cell is solved, cross out that penciled digit that belong to the same row, column and sub-square.
3. If you have done the same exercise for a whole row, check the penciled digits in all the cells of the row to see if a particular digit appears only once! If so, this is the only place where that digit can fit, and so you have just solved another cell.
4. Repeat 3 for columns and subsquares.
5. After you have solved for cells by rows, columns and subsquares, do not forget to modify the pencil marks to reflect the current situation. This is how you would obtain solutions to the remaining cells.
6. Continue this way by repeating the above steps. Most of the time, you will obtain your solution in a short time.

A Sudoku Solver

A sudoku solver has been packaged into a Java applet for your convenience and pleasure. It will solve your problem just like a human being would, showing you the intermediate steps, and highlighting the method used to solve each cell. Best of all, you save all the tedious steps to figure out the candidates, and it does not cost you anything to use it! However, you will need to install Java 2 Run Time Environment (J2RE, version 1.4.2) to execute the applet. If the browser does not invite you to install J2RE, the installation files can be downloaded at Sun Microsystems.

You can enter your own problem by clicking in the squares and entering the numbers. The GO button at the bottom right will cause the applet to do the required calculations and show you the results. The cells that are solved by the applet are coloured and the number prefilled for your convenience. If you agree with the solutions found, just click GO to proceed to the next step, otherwise you could change the numbered squares.

Colour coding:
grey: Single, only one possibility for this cell
magenta: Hidden Single, this candidate occurs only once in the row, column or block
peach: column-block, this candidate within one block is limited to a column or row. Consequently, the candidate in the same column or row can be removed from the other blocks.
jade: block-column, along a column or row, this candidate occurs only in one block. This allows the candidate to be removed from the remaining columns or rows of that block.

Sample Screen

Click here to start applet.

Note: this package is in its early stage of development. If you encounter difficulties, have suggestions for features or comments, please contact:
sudoku@mathpath.net
The best effort will be made to reply in the best possible time, and your understanding is much appreciated.

links:
Solving Sudoku: An excellent article by Michael Mepham.
Sudoku: An interactive collection of puzzles of different degrees of difficulty.
Solving Sudoku: An excellent overview.

Last updated:
2006-01-02 18:17 Links