Stories
Slash Boxes
Comments

SoylentNews is people

SoylentNews is powered by your submissions, so send in your scoop. Only 18 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 mrider on Wednesday July 02 2014, @03:42PM

    by mrider (3252) on Wednesday July 02 2014, @03:42PM (#63101)

    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."

    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2  
  • (Score: 1) by looorg on Wednesday July 02 2014, @05:39PM

    by looorg (578) on Wednesday July 02 2014, @05:39PM (#63160)

    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

      by mrider (3252) on Wednesday July 02 2014, @09:22PM (#63270)

      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."