5 ms·

A sudoku solver in 33 lines of Clojure

148 points by ibdknox 14y ago

ibdknox 14y ago
core.logic is a truly amazing addition to the Clojure ecosystem.
kragniz 14y ago
If you're into short sudoku solvers, here's one in 140 characters (Javascript) from a few months back. http://news.ycombinator.com/item?id=3047148 http://news.ycombinator.com/item?id=3047148
- swannodette 14y ago
  To clarify this code snippet is not just about solving sudoku. This demonstrates brevity, generality, and it's zippy to boot! It's an extensible CLP framework, see my other comment.
  - kragniz 14y ago
    Should I just remove it? It was a knee-jerk reaction to seeing what I thought was just another short suduko solver and was not terribly relevant.
    - swannodette 14y ago
      No other people might miss that point :)
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 ago
  Have 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 ago
    Yes 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 ago
  Very cool! How is this performance achieved? Which algorithm is used to propagate the distinctfd constraint?
  - swannodette 14y ago
    It'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 ago
  I'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!
denniedarko 14y ago
Another Sudoku solver in k, which is only 72 bytes, and a translation into q which is slightly longer for those interested. http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solvers-in-k-and-q/ http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solv...
kleiba 14y ago
Pah, he really should have used TDD... http://ravimohan.blogspot.com.au/2007/04/learning-from-sudoku-solvers.html http://ravimohan.blogspot.com.au/2007/04/learning-from-sudok...
- snprbob86 14y ago
  That was absolutely horrifying. It's like a train wreck. I can look away. I read the entire thing. I'm sure that my thought process while developing code is ugly and messy and scattered too. However, this level of TDD just strikes me as a mechanism to generate legacy code to maintain. It's as if, upon embarking on a new project, these people so miss their giant codebases, with slow builds, and spaghetti grep results, that they have concocted a way to maximize the rate of legacy code generation, so they can feel at home again. The result is that you do a lot of what feels like work. You're constantly moving code around, changing names, tweaking stuff. You tell yourself that you're "Refactoring" and that's how it's supposed to work.
  - saurabh 14y ago
    Exactly. Why would he write tests if it's just play.
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 ago
  Thank for you for the lovely description and insight! :)
- fleitz 14y ago
  Logic 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 ago
  Coding 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 ago
    Just 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.
sadga 14y ago
Confusing post. It's an example of core.logic, not really an interesting Sudoku-solver, as all of the logic is in core.logic
- humbledrone 14y ago
  Confusing post. It's an example of machine code, not really an interesting Sudoku-solver, as all of the logic is in the CPU.
ABS 14y ago
core.logic is awesome and if you want an entertaining introduction take a look at the video of the session that Edmund Jackson did at EuroClojure 2012 https://vimeo.com/45128721 https://vimeo.com/45128721
lrenn 14y ago
For another core.logic example check out the Game of Thrones Genealogy https://gist.github.com/3219448 https://gist.github.com/3219448 h/t @swannodette
- moconnor 14y ago
  Thanks for this, there's some beautiful clojure in there.
blakesmith 14y ago
What happens if you input a puzzle that's unsolvable? Does the program run forever trying to seek a solution, or can it realize the puzzle is unsolvable?
- riffraff 14y ago
  I think you get the core.logic equivalent of prolog's "no" result. I know nothing of clojure and core.logic, but a quick test: *sum=> (run* [q] (fresh [a b] (== a 1) (== b 2) (== a b) (== q [a b]))) () *sum=> (run* [q] (fresh [a b] (== a 1) (== b 1) (== a b) (== q [a b]))) ([1 1]) the first has no solutions, while the latter returns one of them.
Toshio 14y ago
I can't run your code right now, but I'm curious how long it takes to solve this one: http://ompldr.org/vZW4wcw/sudoku.png http://ompldr.org/vZW4wcw/sudoku.png
- zaph0d 14y ago
  It took core.logic ~1100 msecs on my Macbook Air. (time (sudokufd [8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0])) ;; "Elapsed time: 1029.618 msecs" ((8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2))
merraksh 14y ago
This is a solver in 11 lines of AMPL (http://www.ampl.com http://www.ampl.com), a modeling language for optimization problems: param n:=9; set N := 1..n; var x {N,N,N} binary; param fix {N,N} integer; minimize obj: x [1,1,1]; assign {i in N, j in N}: sum {k in N} x [i,j,k] = 1; row {i in N, k in N}: sum {j in N} x [i,j,k] = 1; col {j in N, k in N}: sum {i in N} x [i,j,k] = 1; cell {c1 in 0..2, c2 in 0..2, k in N}: sum {i in (c1*3+1)..(c1*3+3), j in (c2*3+1)..(c2*3+3)} x [i,j,k] = 1; fixit {i in N, j in N: fix [i,j] != 0}: x [i,j,fix[i,j]] = 1; data; param fix: 1 2 3 4 5 6 7 8 9 := 1 1 0 0 0 0 7 0 9 0 2 0 3 0 0 2 0 0 0 8 3 0 0 9 6 0 0 5 0 0 4 0 0 5 3 0 0 9 0 0 5 0 1 0 0 8 0 0 0 2 6 6 0 0 0 0 4 0 0 0 7 3 0 0 0 0 0 0 1 0 8 0 4 0 0 0 0 0 0 7 9 0 0 7 0 0 0 3 0 0; You can solve it by submitting it on line at, for instance, http://neos.mcs.anl.gov/neos/solvers/milp:scip/AMPL.html http://neos.mcs.anl.gov/neos/solvers/milp:scip/AMPL.html (just save it to a file and submit it in the "AMPL model" field). This is an optimization model of an assignment problem. Certain problems should be approached not only with the right language, but also with the right tool. Optimization solvers are not always the best tool for feasibility problems, but this solver (of the branch-and-bound type) can also solve difficult sudoku instances. [Edit: clarification]
cjauvin 14y ago
Maybe this might help some helpless other Clojure newbees like me: I just compiled clojure and core.logic from the github repos, and it seems that the author just changed "everyo" to "everyg" very recently: https://github.com/clojure/core.logic/commit/f831accb0659d04fde043288826942dda6650dfa https://github.com/clojure/core.logic/commit/f831accb0659d04...
- swannodette 14y ago
  Will fix thanks.

148 points by ibdknox 14y ago

core.logic is a truly amazing addition to the Clojure ecosystem.

If you're into short sudoku solvers, here's one in 140 characters (Javascript) from a few months back. http://news.ycombinator.com/item?id=3047148 http://news.ycombinator.com/item?id=3047148

swannodette 14y ago
To clarify this code snippet is not just about solving sudoku. This demonstrates brevity, generality, and it's zippy to boot! It's an extensible CLP framework, see my other comment.
- kragniz 14y ago
  Should I just remove it? It was a knee-jerk reaction to seeing what I thought was just another short suduko solver and was not terribly relevant.
  - swannodette 14y ago
    No other people might miss that point :)

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 ago
Have 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 ago
  Yes 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 ago
Very cool! How is this performance achieved? Which algorithm is used to propagate the distinctfd constraint?
- swannodette 14y ago
  It'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 ago
I'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!

denniedarko 14y ago

Another Sudoku solver in k, which is only 72 bytes, and a translation into q which is slightly longer for those interested. http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solvers-in-k-and-q/ http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solv...

kleiba 14y ago

Pah, he really should have used TDD... http://ravimohan.blogspot.com.au/2007/04/learning-from-sudoku-solvers.html http://ravimohan.blogspot.com.au/2007/04/learning-from-sudok...

snprbob86 14y ago
That was absolutely horrifying. It's like a train wreck. I can look away. I read the entire thing. I'm sure that my thought process while developing code is ugly and messy and scattered too. However, this level of TDD just strikes me as a mechanism to generate legacy code to maintain. It's as if, upon embarking on a new project, these people so miss their giant codebases, with slow builds, and spaghetti grep results, that they have concocted a way to maximize the rate of legacy code generation, so they can feel at home again. The result is that you do a lot of what feels like work. You're constantly moving code around, changing names, tweaking stuff. You tell yourself that you're "Refactoring" and that's how it's supposed to work.
- saurabh 14y ago
  Exactly. Why would he write tests if it's just play.

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 ago
Thank for you for the lovely description and insight! :)
fleitz 14y ago
Logic 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 ago
Coding 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 ago
  Just 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.

sadga 14y ago

Confusing post. It's an example of core.logic, not really an interesting Sudoku-solver, as all of the logic is in core.logic

humbledrone 14y ago
Confusing post. It's an example of machine code, not really an interesting Sudoku-solver, as all of the logic is in the CPU.

ABS 14y ago

core.logic is awesome and if you want an entertaining introduction take a look at the video of the session that Edmund Jackson did at EuroClojure 2012 https://vimeo.com/45128721 https://vimeo.com/45128721

lrenn 14y ago

For another core.logic example check out the Game of Thrones Genealogy https://gist.github.com/3219448 https://gist.github.com/3219448 h/t @swannodette

moconnor 14y ago
Thanks for this, there's some beautiful clojure in there.

blakesmith 14y ago

What happens if you input a puzzle that's unsolvable? Does the program run forever trying to seek a solution, or can it realize the puzzle is unsolvable?

riffraff 14y ago
I think you get the core.logic equivalent of prolog's "no" result. I know nothing of clojure and core.logic, but a quick test: *sum=> (run* [q] (fresh [a b] (== a 1) (== b 2) (== a b) (== q [a b]))) () *sum=> (run* [q] (fresh [a b] (== a 1) (== b 1) (== a b) (== q [a b]))) ([1 1]) the first has no solutions, while the latter returns one of them.

Toshio 14y ago

I can't run your code right now, but I'm curious how long it takes to solve this one: http://ompldr.org/vZW4wcw/sudoku.png http://ompldr.org/vZW4wcw/sudoku.png

zaph0d 14y ago
It took core.logic ~1100 msecs on my Macbook Air. (time (sudokufd [8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0])) ;; "Elapsed time: 1029.618 msecs" ((8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2))

merraksh 14y ago

This is a solver in 11 lines of AMPL (http://www.ampl.com http://www.ampl.com), a modeling language for optimization problems: param n:=9; set N := 1..n; var x {N,N,N} binary; param fix {N,N} integer; minimize obj: x [1,1,1]; assign {i in N, j in N}: sum {k in N} x [i,j,k] = 1; row {i in N, k in N}: sum {j in N} x [i,j,k] = 1; col {j in N, k in N}: sum {i in N} x [i,j,k] = 1; cell {c1 in 0..2, c2 in 0..2, k in N}: sum {i in (c1*3+1)..(c1*3+3), j in (c2*3+1)..(c2*3+3)} x [i,j,k] = 1; fixit {i in N, j in N: fix [i,j] != 0}: x [i,j,fix[i,j]] = 1; data; param fix: 1 2 3 4 5 6 7 8 9 := 1 1 0 0 0 0 7 0 9 0 2 0 3 0 0 2 0 0 0 8 3 0 0 9 6 0 0 5 0 0 4 0 0 5 3 0 0 9 0 0 5 0 1 0 0 8 0 0 0 2 6 6 0 0 0 0 4 0 0 0 7 3 0 0 0 0 0 0 1 0 8 0 4 0 0 0 0 0 0 7 9 0 0 7 0 0 0 3 0 0; You can solve it by submitting it on line at, for instance, http://neos.mcs.anl.gov/neos/solvers/milp:scip/AMPL.html http://neos.mcs.anl.gov/neos/solvers/milp:scip/AMPL.html (just save it to a file and submit it in the "AMPL model" field). This is an optimization model of an assignment problem. Certain problems should be approached not only with the right language, but also with the right tool. Optimization solvers are not always the best tool for feasibility problems, but this solver (of the branch-and-bound type) can also solve difficult sudoku instances. [Edit: clarification]

cjauvin 14y ago

Maybe this might help some helpless other Clojure newbees like me: I just compiled clojure and core.logic from the github repos, and it seems that the author just changed "everyo" to "everyg" very recently: https://github.com/clojure/core.logic/commit/f831accb0659d04fde043288826942dda6650dfa https://github.com/clojure/core.logic/commit/f831accb0659d04...

swannodette 14y ago
Will fix thanks.