A sudoku solver in 33 lines of Clojure | Hacker News Reader

A sudoku solver in 33 lines of Clojure

gist.github.com

148 pointsibdknox37 comments

Code snippet author here.

More details about this code here http://dosync.posterous.com/sudoku and here 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.

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. 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.

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?

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.

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!

Very cool! How is this performance achieved? Which algorithm is used to propagate the distinctfd constraint?

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.

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.

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.

Thank for you for the lovely description and insight! :)

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.

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.

It can be used as an adverb though.

Thanks.

Its 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

Is 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.

Sorry. Right you are. Obviously I completely misread it Humble pie for me. And wow now I understand what the fuss was. That is amazing

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-solv...

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?

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.

This is a solver in 11 lines of AMPL (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 (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]

Pah, he really should have used TDD...

http://ravimohan.blogspot.com.au/2007/04/learning-from-sudok...

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.

Exactly. Why would he write tests if it's just play.

For another core.logic example check out the Game of Thrones Genealogy

https://gist.github.com/3219448

h/t @swannodette

Thanks for this, there's some beautiful clojure in there.

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

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.

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.

No other people might miss that point :)

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/f831accb0659d04...

Will fix thanks.

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

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

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))

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

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

Reply on news.ycombinator.com