Sudoku Problem Solver

This applet demonstrates the solution of a sudoku puzzle by treating it as an NP-Complete problem, rather than through the application of sudoku problem solving strategies.

It's set up here with a 'super fiendish' puzzle from The Times. To set up your own puzzle, use the 'clear' button, and then key in the given values. It doesn't automatically tab, so be careful not to key more than one number in a position. It checks the input, so you'll know if you've keyed wrong.

Use the 'solve' button to set it going. Every one million iterations it will stop and ask if you want to continue. Often, it will complete in less than one million.... usually, no more than three. It's all a question of luck.

To run the puzzle again use the 'reset' button. You can also use the reset button at any point to make small adjustments to the givens.

In common with all the applets on these pages, this one uses a random method. But, unlike the Music Tape applet, this one doesn't simply try random arrangements until it finds one that fits. It wouldn't be possible to do this with today's technology.

There are 6,670,903,752,021,072,936,960 valid sudoku grid arrangements of the 9 sets of 9 numbers. To work through these at ,say, 1 million per second, would take 211 million years.

This applet doesn't look for the combination that fits....it shapes it.

Initially, the given values are set in their places in the matrix from the stock of 9 sets of the numbers 1 to 9. The rest of the stock is allocated sequentially to fill the matrix. The result is far removed from being a valid arrangement. The applet then embarks on a procedure whereby random incremental progressive changes to the non-given elements of the matrix cause it to evolve towards being a valid sudoku permutation. In the case of a a single-solution puzzle like the one here, it will have arrived at the 1-in-6,670,903,752,021,072,936,960 arrangement.

As happens with evolutionary systems, the applet can find itself in a blind alley where, apparently, no further small changes can yield improvement. It doesn't know that it's stuck, it assumes that if it has gone through 100,000 interations and not come to the solution, then it is in a cul-de-sac. To overcome this stalemate it partially scrambles the failed result, before resuming the process. The jerky progress of the applet is a manifestation of this.

When it reaches each millionth iteration point, it is about to restart after being stuck. You have the options of continuing, or resetting. My feeling is that it probably doesn't make a lot of difference which you choose.