Stories
Slash Boxes
Comments

SoylentNews is people

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: 1) by looorg on Wednesday July 02 2014, @05:48PM

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

    Yes. That is what it is. A finite size matrix, with a finite amount of unique variables and a simple set of rules as to how they are to be distributed (one number per cell and no duplicates in rows, cols, boxes). But that isn't what makes them interesting. You are supposed to deduce to solve, not try every possible combo and toss out all the once that result in a conflict.

    Trying every possible combo is like looking at the picture on the puzzle box and conclude "oh look the eiffel tower!" instead of actually solving the puzzle.

  • (Score: 0) by Anonymous Coward on Wednesday July 02 2014, @06:41PM

    by Anonymous Coward on Wednesday July 02 2014, @06:41PM (#63189)

    I made myself a generic Sudoku solver in python (used a sudoku class that did solutions, and you could inherit to change the rules to things like X-sudoku for instance). I used the "Crosshatching", and "Pencilling in" techniques in a 'simple solver' loop, once that failed, I switched to the "pairs" method (actually generalized so I started looking for pairs, then trios, etc.

    Once, the simple method and the pairing methods failed, I switched to brute force for the rest (find a square with 2 choices, create a copy of the board with one of those choices, and try to solve using the previous methods).

    With that program all the effort was in inputting the individual puzzles, running the program was basically instant. I haven't come across a puzzle this solver couldn't handle (other than those sumdokus, or any puzzle with shapes that change from puzzle to puzzle, as those would require me to write a parser that would modify the 'rules' as well as the board, which I just haven't bothered to do).

  • (Score: 2) by FatPhil on Wednesday July 02 2014, @06:56PM

    by FatPhil (863) <pc-soylentNO@SPAMasdf.fi> on Wednesday July 02 2014, @06:56PM (#63196) Homepage
    The smarts in solving sudoku are in working out which cell must lead to a contradition quickly if an incorrect guess is made. Preferably almost immediately.

    Sudoku purists insist that there is not guessing and backtracking, but I take issue with their categorisation. A though process along the lines "This cell can't be A because that would force this other cell to have no possible choices" is precisely what everyone else understands by guessing and backtracking. Ditto "This column needs a B, bit it can't be in any of the free cells apart from this one, as the others leave impossible situations elsewhere". If it requires a stack, or any memory at all on top of the fixed filled-in cells, i.e. it even mentions "other" free cells (as without a stack as soon as you look at the "other" cell, you are forced to forget everything about the previous cell, and therefore cannot draw any conclusions about it, as you don't even know where it was, or even if there was a previous cell you were looking at) then what it's actually doing is equivalent to guessing.

    To demonstrate this, get a sudoku purist shitfaced one evening, and at 7am in the morning wake him up, play really annoying loud music at thim, and force him to solve a difficult sudoku. He won't be able to, as he doesn't have the short term memory required to hold the stack of cells he wants to simultaniously analyse. Give him one that doesn't require any of the macro moves, and he'll have no problem. It's the simultanious analysis of the state of more than one cell that's giving him trouble. E.g. the remembering that one of them might be A or B, whilst he then goes on to see how A or B interfere with the choices of the other cells. They may wrap them up as macros, but it's just a case of well known and well exercised "if A, then if B then failure, else if C then other failure, therefore D". And every "if", as I say, is analogue to a guess.

    Anyway. Sudoku solvers should be written in prolog. Any other type of language is sophomoric.
    --
    Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves