Glover Family Net
Home
Signs of Success
The Mini
Prime Numbers
Sudoku Solver
Wiki Studios
Victoria Glover
Hotloaded Kiwi
SKI Holiday
UK Trip 2009
Queen Charlotte Track
Web Mail
Electric Bike Blog
ough
Sudoku Solver

This page is for solving standard 9*9 Sudoku problems of any difficulty (within reason - the really diabolical ones time out the server - most people will never see one of these type). Enter the digits known into the grid, press solve, and watch it work!


A little bit of fun, and quite a nice PHP coding exercise. The code to solve the puzzle is a tiny 100 lines, and makes use of recursion.The main page is also simple set of loops to validate and display a 9*9 grid of numbers. Simple through hard examples are given (the original test data) to show how it works without all that tedious typing!

Some may consider this a brute force solution, but without getting into geeky stuff that Sudoku solvers are into, it uses quite an efficient method. It does iterate through each cell in turn, looking for cells it can solve directly (where 8 of the 9 numbers are used in the same row, column or square), and continues to iterate through them until no cells are solved. It then chooses a cell with the lowest number of possible solutions, selects the next available solution for the cell, and starts interating through the cells again solving all cells that can be solved. The program is recursive, in that when it next finds a situation where no cells are solved, it repeats the process, looking for a cell in this solution path with the lowest number of solutions, and starting another path. When it gets to a situation where a cell has no solution (all 9 numbers are used in the row column or square already) it knows that the last selection made was incorrect, and drops back to select the next available value for that cell. If all selections for that cell have been used it drops back to the previous level. Eventually, a solution is found if one exists. If more than one exists, only the first found is given.

While researching a bit further into Sudoku, I found the occassional example of incredibly hard puzzles that cause the web version above to time out. Not because of any problem in the code, but because the really hard puzzles take many iterations of the trial and error code, which just takes a long time. Most web servers have a timeout on code running on them, to stop infinite loops, and my provider sensibly has a limit of about 30 seconds.

So I decided to write a stand-alone program. My development tool of choice has been Delphi, with the code in Pascal. Delphi is now the product of a company called Embarcadero, and is expensive and difficult to get a trial of. My daughter discovered a Delphi clone called Lazarus which uses Free Pascal as its programming language. This has turned out to be a really well written and maintained package, more than up to any task I have thrown at it.

I have developed a relatively simple GUI to allow solving of 9 by 9 grids, the source of which can be seen here, and a solver module based on the PHP code used in the online version, which you can see here. And finally, you can download the working sudokusolver.exe file here! I'll be working on a Linux version next, then an android app and possibly an IOS app if I can figure out the Lazarus development environment for these platforms.

Here is a screen shot of the GUI, showing the "World's hardest puzzle" by Arto Inkala, which took 106 milliseconds to solve. This puzzle can also be solved in the Web version, and I still can't find anything harder than this one! but the second image is of "Unsolvable #28'" by David Filmer which may time out the web version (depending on your server), and takes this version 550 milliseconds to solve!

 

Incidentally, a normal hard puzzle from the local paper takes less than 1 millisecond to solve, so no time can be shown (milliseconds being the smallest measurement of time available to a programmer in Pascal).

Both versions now have a statistics line in the results, showing the greatest depth of recursion, and the total number of recursions, as well as the time taken. It's interesting to compare the results for various difficulties of puzzle.

Family Net
Name
Password