# Sudoku

## Rules

For those who do not know, here are the rules of Sudoku. The aim is to fill a 9x9 grid with numbers from 1 to 9 in such a way that each row and each column, as well as any of  the 9 blocks of size 3x3, contain all numbers from 1 to 9 exactly once. A Sudoku puzzle starts with some given numbers, either computer generated or designed by a human. The problem is to fill in in the rest.

## Instructions

The simple Sudoku applet can generate and solve Sudoku problems. There is a popup menu, which can be opened using the right mouse button. Moreover, you can use the mouse to click on the Sudoku fields and select the current position, or to activate the items on the top row of the applet.

### Create a Sudoku Problem

In the popup menu, choose to create a Sudoku. The program will create a Sudoku problem with a unique solution and standard difficulty. You may also create a symmetric Sudoku. See below for more information on the algorithm used.

Moreover, you can create a specific Sudoku in two ways. You can enter a string into the command line below the Sudoku fields, and press enter. This string will be used as a seed for the random generator. A unique Sudoku will be created for each string. Or you can enter or paste a string with exactly 81 characters into the line. The characters in your string will set the Sudoku line by line. 1 to 9 are interpreted as Sudoku numbers, all other characters as empty places. If you create any Sudoku, the input line will contain the 81 characters for this Sudoku with "." for the empty places.

### Solving a Sudoku Problem

To solve a Sudoku, you will have to enter the numbers 1-9 into the Sudoku fields. Click with the mouse on any field to activate it. Then press any of the numbers 1 to 9 on the keyboard, or double click on the numbers 1-9. To clear a position, press 0 or space, or use the 0 item in the row of icons.

You can undo your entries with the backspace key or the - item. Moreover, you can mark the active position in red with the "M". Together with the backspace key, this allows for trial and error solving. However, a good puzzle can be solved without far reaching trial and error.

To assist you in solving, you can highlight all 1s, 2s etc. Click on the items in the top row of the applet to switch highlighting on or off.

If you are stuck, you can let the program solve the Sudoku for you. Just use the menu entry in the popup menu.

### Setup a Sudoku Problem

To enter a problem from the newspaper, start the setup mode with the popup menu. Then you can enter the numbers with the keys 1 to 9, delete numbers with 0. You can move from field to field with the cursor keys.

After you have finished entering, exit the setup mode. The non-empty cells will be protected, and have a slightly darker color.

## Algorithm

This program is the work of one weekend, so the user interface and the algorithms are not too sophisticated.

For solving a Sudoku problem, the program uses backtracking. I.e., it searches for an empty place, fills in all numbers possible by the rules, and starting with each such number, fills the rest of the Sudoku. To reduce the number of branches, the most promising empty field with the least choice of available numbers is tried at first. Properly programmed, this algorithm can solve about 500 puzzles per seconds and GHz.

It is more difficult to generate a Sudoku problem. After some thoughts, I came up with the following idea. Given any solved Sudoku, the program chooses random starting positions, and checks, if the solution is also uniquely determined. To do this, the backtracking algorithm works, until it finds two solutions, or until all choices have been tried. If it is not unique, the solutions are compared, and one of the positions where the solutions differ is added to the start set of given positions. This algorithm produces not too easy problems with a low amount of given numbers.

Generating symmetric problems does not work so well. The problems tend to be too easy. The reason is that I have to add 4 numbers for the symmetry. Currently, I have no good algorithm for this.

When I have another free weekend, I will try to program a solver, which is more oriented towards human thinking, using less backtracking, but more work on the branch cutting. This will allow me to better classify the difficulty of the problem.

## Source

The source and the applet are available. To use the applet elsewhere, you need my permission. The source is only for information. If you want to build on it for an own application or applet, please ask me.

## Problems

Here are some difficult problems, generated by this program.

..6.....89..1..6.7.3.2..1.914.......7.561......39.....6....483..2..3..6....8.9...
4....681...3.......59..86.7.......9..9.285........75288...3.9..24.619...9.6......
.17..3.49.49...12.2.5........2.3....16...7.......856..8..9..4..9...4.35..54......
.2.6.45..3.....4...68..7.3.....2...3.1.5..6..9....6.812..1............14.76.8...5
61....2..3.81.5.9........71......9.85....73.44..619.....4......79.3.......2946...
21...57...5.1.7..6.6.9.8..1.31.9.....4.....6.6.9..41.....47.8......5.91.8......5.