Check out my Sudoku solver

A couple days ago I started solving a few Sudokus. I would say I am average at solving them. I certainly don't use any advanced techniques and I don't really find the difficult ones very entertaining. By difficult here I mean where you have to think several moves ahead to rule out possibilities. So I thought I would write a Sudoku solver. You can try it out. Yeah, I named it 'Jasudoku' after myself. There are some test cases in it, and you can actually play them by entering some numbers and clicking 'Solve' as the program won't let you go to solve mode unless the puzzle is correct at the end.

Anyway, it's a basic solver written in Javascript. It is a very basic program that can pretty much solve the typical Sudoku most people will actually play. So far it's been able to solve all the puzzles generated by the GNOME Sudoku game. However, as I soon found out there are much harder sudokus such as David Filmer's 'Unsolvable Sudoku' 49. My solver can't solve those puzzles.

Update: So, I removed the limit on my solver. It turns out it is not as inefficient as I thought. It can solve all the puzzles, and takes about 46 seconds (on quite an old computer) or just over 100K moves to solve the harder of Filmer's puzzle that I programmed into Jasudoku as a preset.

Arto Inkala is a Finnish mathematician who also creates very difficult Sudokus. One of his puzzles was published in the Telegraph, claiming it was the "World's hardest sudoku", but actually that puzzle is a lot easier than Filmer's puzzles according to the number of moves my solver takes.

Actually, for Filmer's puzzles, the algorithm does find a solution, but I capped the number of moves in my solver at 15000, and Filmer's puzzle takes much longer than that. I limited the number of moves because Javascript is rather slow and would otherwise cause a typical browser to be too unresponsive, and perhaps even crash if you're using an old computer like I am.

There are far more efficient solvers out there such as Peter Norvig's solver. I am probably not going to modify my program to solve Sudokus. First, I like the algorithm that is currently in use, and if I ever get around to porting it to C, it might be a good program to use to benchmark the difficulty of different Sudoku grids. That in turn could be interesting to study the distribution of difficulties. If we could at least empirically estimate the distribution of difficulty across puzzles, then we could estimate how many puzzles of different difficulties there really are. Incidentally, Stertenbrink and later Felgenhauser and Jarvis actually computed that there are

6,670,903,752,021,072,936,960

possible Sudoku puzzles. I didn't check the computation myself, but it seems about right ;). This means that if you could solve a billion of these per second, it would take just over 211 millennia to solve all of them.

I think I've had enough of Sudoku for now. There is a Jasudoku GitHub repository with code licensed under the GPLv3 in case you want to take a look to learn from it.

I also set up a page of the games I wrote in Javascript, which also includes a Minesweeper clone and a Znax clone, both of which have some interesting enhancements compared to the typical original games.

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.