Stories
Slash Boxes
Comments

SoylentNews is people

SoylentNews is powered by your submissions, so send in your scoop. Only 16 submissions in the queue.
posted by LaminatorX on Wednesday July 02 2014, @12:34PM   Printer-friendly
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.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by gringer on Thursday July 03 2014, @01:53AM

    by gringer (962) on Thursday July 03 2014, @01:53AM (#63369)

    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.

    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]
    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2