This is a basic Java Applet that will solve a SUDOKU puzzle for you.

Besides that, this applet has no use whatsoever. This was really just an exercise I made for myself...

Instructions

Enter the values in the grid. When done, click the "solve" button.
If the applet doesn't seem to be able to solve the puzzle, click the 'Interrupt' button
However, so far, this usually indicates a given digit is missing !
All puzzles should take less than 1 second to solve.
The reset button will clear the grid.
When using the interrupt button, it may be necessary to click multiple times (a small bug exists when the interrupt request is sometimes not honored).

How it works..

(a domain is one of 'row', 'column' or one of the 9 3x3 sub-grids)
If the grid is solved (that is, there are no empty cells left) during any of those scans, the process stops.
Also, should the scanner notice that a solution found leads to an impossible puzzle, then the process is also stopped (this occurs if an invalid grid is entered or during the later tentative attempt stages)
If, after a candidate is removed from a cell there is only 1 candidate left, then the cell is deemed to have been solved.
First, all empty cells are filled with all 9 possible candidates. Then a series of 3 standard scans are performed :
  • For each domain, the candidate values which are already present in a non-empty cells are removed for all empty cells in that domain. (For example, if there is a '1' in a row, all '1' candidates are removed from all the empty cells in that row).
  • For each domain, cells are inspected to check if it holds a sole candidate which is then a solution for that cell. (for example, if a cell has a '1' as a candidate but no other cell in a that row has a '1', then '1' is the solution for that cell).
  • For each domain, 2 and 3 candidates cells are checked to see if they have respectivelly 2 or 3 occurences of that same pattern. If a match is found those candidates are removed from all the other cells. (For example, if 2 cells in a row have the only candidates 2 and 8, then all '2' and '8' are removed from the other cells in that row)
    Each of these processes are repeated until the grid no longer changes and a check is made to determine if the grid has changed at all while the 3 processes where executed.
    When this occurs, it is deemed that the puzzle cannot be solved only by deduction. A tentative solution is attempted with a possible candidate in one of the cells and the processes above are repeated until the puzzle is deemed to lead to an impossible solution - in which case that candidate is removed since it creates an impossible puzzle and a new attempt is made starting from the top with that new grid. If no solution is found, another attempt is made with another candidate.
    Should all candidates have been attempted without finding a suitable solution, the tentative approach is tried again but recursivelly. Recursion is only attempted when all else fails. This should not really occur since this would seem to indicate that the puzzle has more than one solution (this assertion is not based on any formal proof - just empirical knowledge)

    Source code

    solvapp.java The front-end GUI
    sudoku/psolver.java An abstract class from which solvers derive
    sudoku/solver1.java 1st stage candidate removal scanner
    sudoku/solver2.java 2nd stage candidate removal scanner
    sudoku/solver4.java 3rd stage candidate removal scanner
    sudoku/solver3.java Tentative solver
    sudoku/cell.java An object representing each cell
    sudoku/puzzle.java An object representing the puzzle
    sudoku/puzzleListener.java The interface for a GUI to monitor scanning progress
    sudoku/puzzleEvent.java An object passed to a listener that describes a scanning event

    Disclaimer

    It's probably very ugly code for those Java wiz out there.. But it was really only an attempt to get reaquainted with the language.. So there are probably a billion comments that can be made on those programs.. Just be forgiving !