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.
Avoid gunfire in the bathroom tonight.
(Score: 0) by Anonymous Coward on Wednesday July 02 2014, @03:55PM
But isn't Soduku just a matrix populated from a finite set of numbers? How hard is it to try all of them and throw out the ones that don't work? I've never played it, because it looked like something a computer could do so easily that I figured there were tons of solutions and a worldwide community of experts who specialized in solving the problem. Maybe there are ways to optimize the solutions, by throwing out ones that you know aren't going to work as soon as you figure that out. I figured a laptop could grind through any small set of matrices with M x N being small enough a human could solve the same puzzle before getting frustrated.
An "elegant" solution to me would be one line of R code that tested all possible matrices and printed the ones that satisfied the parameters.
(Score: 1) by looorg on Wednesday July 02 2014, @05:48PM
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
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
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