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.
(Score: 2) by Nerdfest on Wednesday July 02 2014, @12:42PM
I had a look at the source code for a few. This is obviously some meaning of the word "elegant" I wasn't previously aware of. They're reasonable clean and well formatted solutions, but I'd be very hard-pressed to call them elegant. In general, I don't think purely procedural languages are not made for 'elegant' solution. Fast? Sure. Straight-forward? If well written, yes, but they generally end up being longer than more 'elegant' solutions in object oriented or functional languages. That's not to say those approaches are necessarily better. If you're not careful, elegant can drop off the cliff to obscure.
(Score: 2, Funny) by middlemen on Wednesday July 02 2014, @01:35PM
The summary means "elegant FORTRAN" not "any" elegant code in general. FORTRAN code can look really ugly and like Python needs a lot of formatting !
The most elegant code to solve Sudoku in my fictional language titled "sudokoo" is as below:
solve sudoku || sudo solve sudoku
(Score: 2, Interesting) by Anonymous Coward on Wednesday July 02 2014, @01:41PM
Yeah except it's written in F90 so it doesn't need fixed-form formatting at all, and it isn't written FORTRAN but Fortran. The formatting requirements for "modern" Fortran -- and it's stretching it a bit to describe a 15 year old standard as modern -- are barely more stringent than those for C or C++. One can write perfectly elegant programs in F90 and beyond, so long as one's view of "elegance" doesn't rule out "end if" and "end do" statements.
(Score: 3, Funny) by wonkey_monkey on Wednesday July 02 2014, @01:28PM
Is there a fast, elegant program to tell us what a computational nanoscientist is?
systemd is Roko's Basilisk
(Score: 1, Funny) by Anonymous Coward on Wednesday July 02 2014, @01:33PM
Yes, but you need to delve deep in metaprogramming.
(Score: 4, Funny) by EvilSS on Wednesday July 02 2014, @01:53PM
Yes, you can actually run it online from this link [google.com]
(Score: 2, Insightful) by jelizondo on Wednesday July 02 2014, @02:10PM
From Calcudoku.f90
! 6 is the maximum number of cells that a cage can have.. since all the numbers
! belonging to a cage must be unique..
INTEGER, PARAMETER :: max_cells_in_cage = 9
Great comment, 6 is the maximun and then goes to declare the parameter as 9.
Elegant? No. Cute? No.
(Score: 1) by karmawhore on Wednesday July 02 2014, @02:37PM
There as a typo in the coment. Does that disqualify it for elegant/cute status?
=kw= lurkin' to please
(Score: 2) by TGV on Thursday July 03 2014, @05:20AM
Well, as a comment, it's rather superfluous. It's nearly the level of i++; // increase i by 1
(Score: 2) by KritonK on Thursday July 03 2014, @09:06AM
Nearly, indeed. It's more like
i++; // increase by 2
(Score: 2) by gman003 on Wednesday July 02 2014, @02:11PM
I was stumped by the 36 Cube puzzle for the longest time. I could get 34 out of the 36 right, rather easily actually, but the last two always conflicted. I eventually wrote a program to brute-force it, finding every possible solution (I figured if I wrote the program, it was still me beating the puzzle, I was just using a tool).
There were none. Zero valid solutions.
The puzzle is literally impossible as described - you have to notice, somehow, that two of the pieces will fit into two certain spaces that no other piece of that size will.
(Score: 2) by VLM on Wednesday July 02 2014, @02:39PM
Source in a pkzip file? Haven't seen that since msdos times in the early 90s. Put it up on github.
One thing that I see people hanging up on is there's elegance as a programmer without knowing the .biz logic and theres elegance as a puzzle solver as in having great algos and rarely are the two identical. So not willing to look at the source I wonder which way these go. Given the comments by programmers making fun of the code, I think we can assume its elegance as in puzzle solver / algo elegance not elegance as in pretty looking stylish source code.
(Score: 0) by Anonymous Coward on Wednesday July 02 2014, @11:51PM
I've gotten distros from github in .ZIP files
Windows supports zipfile decompression making them look like folders and
files within folders when you click on them.
To bad Phil Katz isn't around to see his file format still in use to this day.
http://en.wikipedia.org/wiki/Phil_Katz [wikipedia.org]
His legal problems with System Enhancement Associates notwithstanging....
(Score: 1) by looorg on Wednesday July 02 2014, @03:00PM
I'm not really sure that this is all that impressive. It's a fine programming exercise but isn't that all it is? A five year old computer (or cpu) can still push out a millions of instructions and calculations per second, many more then my brain will. I'm not an expert fortran programmer but this looks like yet another bruteforce solver to me. 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.
Finding a solution might be interesting but being able to explain the solution is always interesting. "I tried every possible combo until one fits" just isn't a very interesting solution method. It is simplistic and brutish, it is not elegant.
For pen and paper solutions for some really hard puzzels you can sometime resort to a version of this. Eventually you tend to land in a scenario where you have lots of pairs and trippels etc and you can't spot the pattern and the easiest way forward is to just pick a pair and do a "what if this was X scenario" and see if it pans out. It works, it just isn't what I would call elegant.
(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.
(Score: 2) by mrider on Wednesday July 02 2014, @03:42PM
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."
(Score: 1) by looorg on Wednesday July 02 2014, @05:39PM
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
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."
(Score: 2) by gringer on Thursday July 03 2014, @01:53AM
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]
(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
(Score: 2, Informative) by Anonymous Coward on Wednesday July 02 2014, @04:04PM
The algorithm is simply:
1. Go to next empty cell. If no empty cell, puzzle is solved, exit
2. For each possible value for that cell (such that there are no row/column/box conflicts), assign that value and return to #1. If no solution was recursively reached, make cell empty again.
It works, but it's just one step above pure brute force. Not novel in any way.
Not only that, but the way he's implemented it is really efficient. I could easily reduce it to half the lines of code.
And its barely even readable code. He declares variables such as "i", "ii", "iii", "iiii", "ith", "j", "jj", "jjj", "jth"... And some of the variables he declares and assigns aren't even used.
This is something a freshman computer science student would turn in for homework and get a 'B' on. NOT news material.
(Score: 2) by TGV on Thursday July 03 2014, @05:26AM
I thought you were joking, but no, the Sudoku_solver is precisely as you describe. It's awful. The other variable names in the core routine are small_cell_row,small_cell_column, value1,value2,value3,value_cells1,value_cells2,value_cells3. That's unreadable.
I think said freshman should be glad with a C.
(Score: 2, Informative) by dbe on Wednesday July 02 2014, @06:30PM
Sudoku is an exact cover packing problem. It's difficult to do more efficient than Knuth Dancing link algorithm (http://en.wikipedia.org/wiki/Dancing_Links).
Cheers
dbe