During the Christmas holidays a couple of years ago, I wrote a program in C# to solve Sudoku puzzles. My first attempt was able to solve some puzzles but not all of them. I realised that I did not know enough about Sudoku solving strategies and I ran out of time (the holidays came to an end), so I left it for a while.
A few months ago I bought a book entitled "How To Do Sudoku" by Carol Vorderman and I got stuck into learning to solve Sudokus starting with easy puzzles, all the way through super difficult ones.
Armed with more knowledge, I decided to have another go at writing the program and I am delighted with the results. I managed to get it right this time, using a recursive, back-tracking algorithm. I am pleased to say my second attempt can solve any Sudoku that is solvable.
It solved this "super difficult" puzzle from Carol's book, which she says would take an expert around an hour (it took me almost 2), in just 228 milliseconds!
Zero represents a blank cell:
000 000 000
000 390 280
040 021 093
600 070 900
900 502 006
005 060 001
180 250 030
064 018 000
000 000 000
Here is the output from the program:
SOLVED after 496 recursions in 228 milliseconds
239 485 167
751 396 284
846 721 593
628 173 945
913 542 876
475 869 321
187 254 639
364 918 752
592 637 418
Saturday, June 09, 2007
Subscribe to:
Post Comments (Atom)
2 comments:
Cool, I once found a blog post that explained a neat algorithm for solving Sudoku. I'm sure I bookmarked it but I have never been able to find it since.
I imagine that with enough time and effort you could create a program for your N95 that lets you capture the grid using the camera and then solves it. I wonder what the state of OCR software for S60 is?
Thanks Steve. That sounds like quite a challenging one to take on. I think it's time I got hold of a dev kit for S60.
Post a Comment