4 ms·
Code snippet author here. More details about this code here http://dosync.posterous.com/sudoku http://dosync.posterous.com/sudoku and here http://dosync.poster
by swannodette 14y ago
Code snippet author here.
More details about this code here http://dosync.posterous.com/sudoku http://dosync.posterous.com/sudoku and here http://dosync.posterous.com/friendlier-shorter http://dosync.posterous.com/friendlier-shorter
This is based on the excellent work of Claire Alvis, Will Byrd & Dan Friedman who continue to improve their Scheme miniKanren system. miniKanren embeds Prolog semantics into Scheme. core.logic implements and extends that work in Clojure. This code highlights the new cKanren extensions Claire et. al. have developed which enables Constraint Logic Programming in miniKanren - http://en.wikipedia.org/wiki/Constraint_logic_programming http://en.wikipedia.org/wiki/Constraint_logic_programming.
One neat bit about this is that this is surprisingly efficient given the generality and how new this work is. The HN crowd will be familiar with Norvig's fantastic sudoku solver in Python - http://norvig.com/sudoku.html http://norvig.com/sudoku.html. This core.logic solver can solve easy sudoku problems ~6-7ms. Norvig's hard one that takes 188 seconds in Python takes ~60ms. More benchmarking needs to be done, but this is promising especially since this is a generic all-different FD constraint over small domains as well as intervals - so it's not specific to sudoku.
Feel free to ask any questions.
UPDATE: to be extra clear this is not just about sudoku. The following is also now possible to express under the same framework -
(run* [q]
(fresh [x y z]
(infd x y z (interval 1 3))
(+fd x y z)
(== q [x y z])))
;; => ([1 1 2] [2 1 3] [1 2 3])
This program shows all possibilities where x, y & z range over 1, 2, 3 where x & y add up to z.
- bfe 14y agoHave you found any multiple-order-of-magnitude spike of processing time for any other "hard" ones? Or, more generally, any quantization of time as a function of difficulty?
- swannodette 14y agoYes I had time to check that one of the hardest ones listed on Wikipedia takes ~570ms on my machine, so that's nearly 100X slower. I haven't had time yet to do any real comprehensive benchmarking or quantization a la Norvig. Hopefully soon.
- deleted 14y ago[deleted]
- jules 14y agoVery cool! How is this performance achieved? Which algorithm is used to propagate the distinctfd constraint?
- swannodette 14y agoIt's a mix of Claire et al's ideas and my own. A distinctfd constraint takes a list of vars and creates the real distinctfd constraint for each var, these are put into the constraint store. They do not run unless the var reaches a single possible value. At which point they run once and are purged from the constraint store. Each constraint has a list of the vars involved plus the list of known single values for the other vars. When it runs if the constrained vars' value exists in the single values set it fails. If it doesn't, the constraint removes the value from any other var that has a domain of values. It's actually pretty simple. Most of the performance is from Clojure, the purely functional design which gives us backtracking "for free", and the random access nature of the constraint store.
- markus2012 14y agoI've been anxiously waiting for you to make this available for some time. All other personal coding projects are now secondary to this. I can't wait to play!