4 ms·
People thinking "Oh god, not another x in y lines of z" (I first thought this as well), be open minded and try to read the code. It might not be in a language y
by JeanPierre 14y ago
People thinking "Oh god, not another x in y lines of z" (I first thought this as well), be open minded and try to read the code. It might not be in a language you know, but try and see if you can understand the last part:
(run 1 [q]
(== q vars)
(everyo #(infd % (domain 1 2 3 4 5 6 7 8 9)) vars)
(init vars hints)
(everyo distinctfd rows)
(everyo distinctfd cols)
(everyo distinctfd sqs))
Which, for me, reads "Take one solution and return q, where q is equal to vars, and every var is either 1, 2, 3, 4, 5, 6, 7, 8 or 9. Then initialize the variables with the already placed elements we've been given, and ensure that every row, column and square has only distinct elements."
Now, I don't know about you, but this sounds actually like the rules of Sudoku for me, not some algorithm on how to solve it. That's amazing, and should really get you to think about trying out logic programming if you haven't already. There's a lot of power in it, and using it in production code might not be as far away as it seems.
- swannodette 14y agoThank for you for the lovely description and insight! :)
- fleitz 14y agoLogic is a much better way of programming than poking and prodding bits. Turns out that a computer is much better at turning logic into poking and prodding than turning poking and prodding into logic.
- icebraining 14y agoCoding in Prolog feels very much the same, 'though the syntax is frustrating. My solver came out somewhat more declarative but a little more verbose, 'though.
- sirclueless 14y agoJust FYI, "though" is an English word, synonymous with "although." It doesn't require an apostrophe, and in fact "although" is incorrect when used at the end of a sentence.
- icebraining 14y agoThanks.
- kurige 14y agoIt can be used as an adverb though.
- twelvechairs 14y agoIts very nicely coded and credit to the author, but I think people might infer from your description something more than its actually doing, which is basically 'brute force' - trying every combination and crossing them off when they fail (hence your quoted code above). The alternative approach would be to work like humans do, looking for the next 'right' square (rather than this, which looks for the next 'wrong' combination). This would be much more difficult but would solve the hard problems much faster and computationally elegantly (though its only a matter of seconds anyway!). [EDIT] I created an derivative version in ruby for anyone who is interested (42 lines of code - probably could be shorter) - http://pastebin.com/ecjQzzU6 http://pastebin.com/ecjQzzU6
- riffraff 14y agoIs this really what is happening? I don't understand much clojure but looking at it it would seem to me the solution is actually found in a smart way, iteratively restricting the domains for a single variable and then propagating the changes (which I think is the standard constraint programming approach). In ruby you'd do something similar with gecoder.
- twelvechairs 14y agoSorry. Right you are. Obviously I completely misread it Humble pie for me. And wow now I understand what the fuss was. That is amazing