SoylentNews is people
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.
A vivid and creative mind characterizes you.
(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.