I love sudoku puzzles
Posted by ajay on January 16, 2007
I am writing a post again after a long time. Didn’t write one primarily due to the fact that I was very much busy these days due to Hectic schedule at college and ofcourse some other things ;). Anyway In vecations I wrote a kind of interesting c++ program to solve sudoku puzzles given in daily news papers. The program uses backtracking and thats why It’s complexity is exponential in general. But still on most of the puzzles that I tried; It works very fast ( almost negligable run time). You can download it or have a look at it here. If you find input puzzles where it doesn’t work ( bugs ) or you have better ideas to solve a sudoku puzzle ( in terms of run time ofcourse ), then please post it as a comment.
PS 1: The program is primarily written to solve puzzles of size 9 x 9. but can be easily modified to solve a bigger puzzle.
PS 2: I have been trying to solve this problem. But my idea doesn’t seem to run in time :(. If anybody solves it, please post a comment about the idea used to solve the problem. ).
Just another tech blog. 
Turbo said
Nothing about the sudoku program, but about the template.
Instead of this:
#define FOR(i,a,b) for(int i=(int)(a);i
use this:-
#define FOR(i,a,b) for(int _n=(int)(b),i=(int)(a);i
I saw tomek using it. I guess you know why its better, but just for the sake of completeness, if you pass something.size() as b, then something.size() will be calulated in each loop. And all stl containers do not have O(1) size() functions. But be careful. Don't use it for the case where the size of the container changes withing the loop(for example, if you use erase function within the loop).
And of course, good work with the sudoku puzzle!
ajay said
@Turbo.
Thanks for spotting that out. I’ll change it now. 🙂
Brandy said
i need them to debut to win the bet, that $20 is mine~ XDHm, half of them are debuting, maybe you can still get $10?sexy zone doesn’t have a very voellyball-ish sound for a volley ball support song…Yeah, that’s what I’ve been thinking too. Then again, we’ve only heard 6 seconds of it, so maybe there’s still hope. XD
haryiips said
nice job man…….//
Sharad Upadhyay said
I see that you have also solved 16×16 puzzle on spoj. What about posting the alorithm here?
ajay said
@Sharad.
Yeah Why Not. First of all SUDOKU is known to be an NP complete problem ( a type of exact cover problem ) so you can only optimize your backtracking to get accepted on this problem. I have used a technique called “Dancing Links” from Knuth. This technique is used to efficiently implement backtracking solutions for a class of problems commonly known as “Exact Cover” Problems. To see what an exact cover problem is and how is it related to SUDOKU puzzles this link might be helpful. -> http://en.wikipedia.org/wiki/Exact_cover . To know about Dancing Links ( commonly known as DLX ) an introduction can be found here -> http://en.wikipedia.org/wiki/Dancing_Links . After you go through these pages, some help regarding implementation of Dancing Links can be found in this research paper by Knuth -> http://xxx.lanl.gov/PS_cache/cs/pdf/0011/0011047.pdf .
Using DLX you can easily get a runtime of around 1 seconds in the problem. I hope my explanation helps.
Sharad Upadhyay said
Yes, that works.
In fact I was curious how you get the best time of 1 sec on spoj. Probably everyone there(on spoj) is trying to solve it by DLX. If fact your best time inspired me. I got it 0.84 sec but for it some credit goes to you also.
Initially I thought using some smart backtracking but it didn’t work. Do you know someother way to solve it (without DLX)? I tried simple backtracking and it didn’t give me solutions even running the program for 24 hours on my machine.
ajay said
Well there are some methods which approach to solve a puzzle as a human brain will solve it .. and those are much faster. But I’m not clear about any of them. Googling might give you many results.
abhijeet said
Gishmo kid…Ajay SHomani……..[:D]
Nilay Vaish said
Have look at this link. It is from Google’s Director of Research, Peter Norvig.
http://norvig.com/sudoku.html
murali said
sir,
I dont understand many aspects in your code like “memset(),why all the bool arrays are used.
so i request you to put the comments for all these parts of code.
rapheal said
Hey, nice job. Im trying to add something like puzzle generator in a case where the user doesnt want to input his own puzzle but just to solve a puzzle generated by the program. Please could you give me an idea of how to do this.
Justine Beiber said
Nice posts but I’m looking for the Algorithm codes for my Puzzles Sudoku site. Thanks!
Harris said
Well done, thanks!