Sudoku Solver
This is a Sudoku solver I wrote in Java a while back. Here it is running in the browser.
Please feel free to type in the hardest Sudokus you can find anywhere, and let me know if it can solve them, I haven't found any it can't yet.
The Java has been converted to in-browser Javascript by Google Web Toolkit.
The algorithm works by backtracking, i.e. simply going through all squares from top-left to bottom-right, and finding the set of "candidate numbers" for that square (i.e. which numbers are not already used on that row, column or 3×3 block). The first candidate number is "applied" by placed it into the square, and the algorithm moves to the next square. If there is a square where the set of candidate numbers is empty (i.e. no number would work, given the candidates applied in previous squares) then the system returns to the previous square and tries the next candidate for that square. Once the system has gone "beyond" the bottom-right square, then the set of applied candidates consitutes a solution. However, backtracking continues, if the system reaches beyond the bottom-right square again, then the previously found solution
was not unique, and the algorithm terminates. Once the system has backtracked back to the start, if a single solution was found then it is a "unique solution" (success case), otherwise if there are no solutions then the Sudoku is unsolvable.
By the way, Internet Explorer really isn't that fast; I appreciate that is well-known to anyone who's ever read Google Chrome marketing material! But the Sudoku here takes 708ms to solve on IE8, 334ms on Firefox 3.6, about 100ms on Safari 4 and Opera 10, and 49ms on Chrome 4, on this 2.3GHz/core Intel Windows Vista computer.
Alas there were Sudokus which took too long for the original synchronous approach (i.e. user clicks, do calculation, update the screen with the results). So now, in the case the calculation takes too long, a "worker" is spawned, which does the calculation, and the spinner is displayed in that case.
See the source on github.