SoylentNews is people
SoylentNews is powered by your submissions, so send in your scoop. Only 11 submissions in the queue.
SoylentNews
posted by
LaminatorX
on Wednesday July 02 2014, @12:34PM
from the Which-Door-would-He-Suggest? dept.
from the Which-Door-would-He-Suggest? dept.
Computational nanoscientist Surendra Jain has written solvers for Sudoku,
Killer Sudoku, Samurai Sudoku, Calcudoku, Kakuro and many other
logic problems.
All are elegantly coded and very fast: for example,
the "World's Hardest Sudoku" is solved in 0.05 seconds (on a 5 year
old PC) and his Knight's Tour solver is an order of magnitude faster
than this one.
The page (called "Classical Geek") has all source (in Fortran 90,
one of the most popular languages in high-performance computing)
as well as compilation and running instructions.
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Must I hold a candle to my shames?
-- William Shakespeare, "The Merchant of Venice"
(Score: 1) by looorg on Wednesday July 02 2014, @03:00PM
I'm not really sure that this is all that impressive. It's a fine programming exercise but isn't that all it is? A five year old computer (or cpu) can still push out a millions of instructions and calculations per second, many more then my brain will. I'm not an expert fortran programmer but this looks like yet another bruteforce solver to me. If i'm not misstaken it looks at cells with few options and try all the possible combos and see if one fits? I could be wrong. But arn't these puzzels supposed to be be solved by logical steps and not by trying every possible combination until one fits; which is the brute force method.
Finding a solution might be interesting but being able to explain the solution is always interesting. "I tried every possible combo until one fits" just isn't a very interesting solution method. It is simplistic and brutish, it is not elegant.
For pen and paper solutions for some really hard puzzels you can sometime resort to a version of this. Eventually you tend to land in a scenario where you have lots of pairs and trippels etc and you can't spot the pattern and the easiest way forward is to just pick a pair and do a "what if this was X scenario" and see if it pans out. It works, it just isn't what I would call elegant.
(Score: 2) by opinionated_science on Wednesday July 02 2014, @03:32PM
i must admin , i sort of agree. i would like to see the *shortest* solution to sudoku - i suspect the solution could be found statistically without much code at all!!
(Score: 2) by mrider on Wednesday July 02 2014, @03:57PM
Possibly. The fastest one I've written (in C - and it's too ugly to publish) searched through the cells looking for the one that had the fewest number of possible choices. If I found a cell where only one choice could possibly work, I filled that in immediately and started over. If I didn't, then I pushed the current state onto the stack along with the possible choices for the cell with the fewest possibilities. Then I would try those possibilities to see where they went.
A hand-crafted puzzle, specifically designed to be worst-case for my program would take about .1 seconds on my computer. A general puzzle would take between .03 and .08 seconds depending on complexity. There's probably some algorithmic speed to gained by a better programmer than I, but I suspect most speed up would require writing better C code rather than improving the algorithm.
Doctor: "Do you hear voices?"
Me: "Only when my bluetooth is charged."
(Score: 1) by looorg on Wednesday July 02 2014, @05:41PM
I agree, that would be a lot more interesting in my mind then to see how many seconds, or fractions of a second, it took a computer to brute force something. Shortest solution or fewest steps or whatnot.
(Score: 2) by mrider on Wednesday July 02 2014, @03:42PM
I'm not sure I'm reading your "brute force" description properly, so maybe I'm taking this the wrong way. But (at least in Sudoku) there's always a certain amount of brute force involved. Depending on the puzzle, there may come a time where there are no cells where only one choice fits. Sometimes one simply has to think "Well, first I'll try '2' and see where that leads. If that fails, I'll go back and try '7'.
Having said that, I don't see any place where the author walks through the puzzle looking for the cell with the fewest choices. So in this case it in fact does look like a really fast, true brute force approach.
Of course, I know jack shit about Fortran, so maybe I may very well be reading his/her code incorrectly.
Doctor: "Do you hear voices?"
Me: "Only when my bluetooth is charged."
(Score: 1) by looorg on Wednesday July 02 2014, @05:39PM
I disagree. Brute force is not the method you are supposed to apply to solve, most common, sudoku puzzles. Certainly not so regarding the once that are printed in most common newspapers and similar. You are supposed to deduce what goes into what cell/box/row/col and not just try (every) possible combination or to see what happens if you try this or that. If that is how you solve them then you are doing it wrong.
But as I stated in some hard, or designed to be hard, cases such as the one mentioned in the article as "world's hardest sudoku" that doesn't always work for you, for one reason or another, and you are more or less forced to have to resort to that kinda of guessing or scenario thinking (what you refered to as try 2 and if that fails try 7). In the last couple of sentences in my post I called that the 'what if scenario'; you might call it trial and error or whatever you like. As noted it works but it isn't elegant, it is a very crude and brutish solution method.
But as I mentiond I might also have read the code wrong, I have not looked at fortran code this century so I might have been fooled. Either way I'm fairly confident it's a brute force solver and nothing else.
(Score: 2) by mrider on Wednesday July 02 2014, @09:22PM
After reading your post, it seems we are agreeing even though we appear to disagree. True "brute force" is dumb. What I called "there's always a certain amount of brute force involved", you called "what if". Same basic point. The point being that there are times where it's not possible to find a cell that has precisely one answer. However, it's always possible to find a cell that has a reduced number of answers (unless the puzzle is totally blank and you on the first cell...). It would be dumb to ignore those cells, and it would also be dumb to try numbers that can't possibly work in those cells.
Doctor: "Do you hear voices?"
Me: "Only when my bluetooth is charged."
(Score: 2) by gringer on Thursday July 03 2014, @01:53AM
Yes, that appears to be the case. This also means that using this solver to generate puzzles will end up in pain and misery.
I am of the opinion that a proper sudoku solver should be able to give an "I don't know" answer (or perhaps, "that looks ambiguous") in response to the question, "can this be solved?" My J2Me sudoku puzzle generator / solver does this, and will correspondingly only generate puzzles that are unambiguous (although they might be a bit too easy for experienced sudoku players):
http://users.actrix.co.nz/jessicac/JMeSudoYu.jad [actrix.co.nz]
However, the one here does not deal approriately with ambiguous puzzles. The following puzzle is ambiguous, because both 1 and 2 can satisfy a correct solution when placed in the top left hole:
0 0 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3
0 0 4 3 6 7 8 9 5
8 6 7 9 1 5 3 4 2
3 9 5 8 4 2 6 7 1
5 7 1 6 9 4 2 3 8
6 4 2 5 3 8 9 1 7
9 3 8 2 7 1 5 6 4
The fortran code provided here will give a solution for this puzzle, when the correct answer should be "ambiguous". Because the problem space of sudoku is not fully known (i.e. there are some hard puzzles that have only one solution, but brute force is necessary to find it), a brute force algorithm is necessary if you want to verify that a puzzle is truly ambiguous, but giving an "I don't know" answer is very possible without brute forcing things.
Ask me about Sequencing DNA in front of Linus Torvalds [youtube.com]