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.
Of course you have a purpose -- to find a purpose.
(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."