It's a long time since I know about the Sudoku puzzle. I've never been drawn to it, although I did think occasionaly that it would be an interesting programming exercise to implement a solver for that. Few days ago I learned about the variant called "killer sudoku" which is supposed to be harder than plain sudoku. So I set out to write a solver for that variant.
My first idea was to write the program in GNU prolog, using its finite domain solver. But then I said, heck! Let's see whether the brute-force method is feasible. And indeed, it turns out that it is. You can download the solver coded in C++ here. The user interface is lacking, but the program does what it is supposed to. On 2GHz Pentium M, the easiest (as classified by the problem setter) is solved in 5ms, and the hardest in 400ms.
One thing is bugging me though. Sudoku puzzles are supposed to be solved by logic, without guessing. How do you explain that the brute-force solver, which is employing always the same "dumb" strategy of guessing and backtracking, takes the time proportional to the puzzle level? "Harder" puzzle should imply harder logical reasoning. I fail to see the connection between "harder" logical reasoning and the amount of work the brute-force solver has to perform. Somehow I think that these two are independent.
Tags: sudoku
skip to main |
skip to sidebar
This is the repository of my wild thoughts, general comments and ideas that I don't have the time to actually work on.
4 comments:
Do you know asymptotic upper bound (big O) of your algorithm (I didn't looked at the code)? It seems to me that no better algorithm than simple exhaustive search will do the job (thus, I would bet on O(n^2) algorithm).
If you read the README file, you will get an URL to the description of the "killer sudoku" variant.
Yes, the program does the exhaustive search, that's what I have also written in the blog entry :) Its upper bound therefore exponential (and NOT quadratic, as you have written).
The original sudoku has been reduced to the set cover and graph colouring problems which are proven to be NP complete. Read a bit on Wikipedia about sudoku, they also have a mathematical analysis section.
Yes, sorry on typo, it is O(2^n), not O(n^2).
Btw, I just noticed that the HTML code for the comment is generated wrong (it displays text /*, not the italic font). For example, try to type some text between html tags for italic font. You should get something like this:
Test (test)
Is the program mirrored anywhere else? The above link doesn't seem to work anywhere.
Post a Comment