Skip to content

Instantly share code, notes, and snippets.

@swannodette
Created July 31, 2012 14:52
Star You must be signed in to star a gist
Save swannodette/3217582 to your computer and use it in GitHub Desktop.
sudoku_compact.clj
;; based on core.logic 0.8-alpha2 or core.logic master branch
(ns sudoku
(:refer-clojure :exclude [==])
(:use clojure.core.logic))
(defn get-square [rows x y]
(for [x (range x (+ x 3))
y (range y (+ y 3))]
(get-in rows [x y])))
(defn init [vars hints]
(if (seq vars)
(let [hint (first hints)]
(all
(if-not (zero? hint)
(== (first vars) hint)
succeed)
(init (next vars) (next hints))))
succeed))
(defn sudokufd [hints]
(let [vars (repeatedly 81 lvar)
rows (->> vars (partition 9) (map vec) (into []))
cols (apply map vector rows)
sqs (for [x (range 0 9 3)
y (range 0 9 3)]
(get-square rows x y))]
(run 1 [q]
(== q vars)
(everyg #(infd % (domain 1 2 3 4 5 6 7 8 9)) vars)
(init vars hints)
(everyg distinctfd rows)
(everyg distinctfd cols)
(everyg distinctfd sqs))))
;; ====
(comment
(sudokufd
[0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0])
)
@swannodette
Copy link
Author

@ioquatix
Copy link

ioquatix commented Aug 2, 2012

Is it fast? If you add support for this format I'll test it: http://www.codeotaku.com/blog/2011-05/university-sudoku-challenge/index

@swannodette
Copy link
Author

It seems reasonably fast in terms of the generic all different constraint, but no it's not designed to compete with specialized sudoku solvers.

@Gonzih
Copy link

Gonzih commented Aug 4, 2012

I was trying to run following code ang get error:

Caused by: java.lang.RuntimeException: Unable to resolve symbol: everyg in this context

Seems like i'm doing something wrong, any suggestions?

Thanks

@cjauvin
Copy link

cjauvin commented Aug 4, 2012

@Gonzih This should be solved by updating to the latest version

@swannodette I'd like to understand..

(run* [q]
      (fresh [x y z]
           (infd x y z (interval 1 3))
           (project [x y z] (not= (+ x y) z)) ;; <-- ..why doesn't this work as the opposite of +fd??
           (== q [x y z])))

@Gonzih
Copy link

Gonzih commented Aug 4, 2012

@cjauvin latest version of what?

my project.clj

  :dependencies [[org.clojure/clojure "1.4.0"]
                 [org.clojure/core.logic "0.8-alpha1"]]

Thanks

@cjauvin
Copy link

cjauvin commented Aug 4, 2012

I don't know to what version it corresponds, but take a look at this commit log (I guess it's post 0.8-alpha1):

clojure/core.logic@f831acc

I actually had the opposite problem:

http://news.ycombinator.com/item?id=4330999

@swannodette
Copy link
Author

@gonzH apologies. The everyo -> everyg rename was not in alpha1, I've released alpha2 which should show up on the maven repos in 24 hours or so. In the meantime you can use core.logic master.

@swannodette
Copy link
Author

@cjauvin, it's not clear to me what you're trying to accomplish. project will walk a variable, get it's value, and give it a local name. You'll have an internal representation of core.logic intervals for which the Clojure arithmetic operators don't work.

@cjauvin
Copy link

cjauvin commented Aug 6, 2012

I am not trying to accomplish anything in particular, apart from simply trying to understand the small example you gave in one of your comments on the HN thread (which has proven to be surprinsingly harder than I assumed, perhaps due to the fact that my Prolog skills are farther than I thought, and/or that the CL doc is rather sparse for the moment). In particular, I wanted to understand how to reverse the goal (i.e. find the triples for which x + y != z). My first attempt was to use the "disequality" contraint, but since I could not make sense of its result:

(run* [q]
    (fresh [x y z]
        (infd x y z (interval 1 3))
        (+fd x y z)
        (!= q [x y z])))
;; => ((_.0 :- (!= _.0 [<lvar:x_4549> <lvar:y_4550> <lvar:z_4551>])))

my second attempt was the code I posted earlier (using "project"). I now understand that an interval is a special CL object that does not interoperate with normal Clojure arithmetic ops, and I guess it means I would have to write a function similar to "+fd", but unfortunately that's where it stops for me, as I simply cannot understand its source code for the moment.

@swannodette
Copy link
Author

@cjauvin

  (run* [q]
    (fresh [x y z n]
      (infd x y z n (interval 1 3))
      (+fd x y n)
      (!=fd z n)
      (== q [x y z])))

Is probably what you want.

@cjauvin
Copy link

cjauvin commented Aug 7, 2012

It makes good sense.. many thanks! I guess I'll have no other choice than to go through The Reasoned Schemer, to go deeper.

@postspectacular
Copy link

Hey David, where did "infd" go? It's nowhere to be found in the master branch. thx!

@orb
Copy link

orb commented Jun 28, 2013

@postspectacular - it's in clojure.core.logic.fd now. Here's an updated version that I've been using in my core.logic talks:

https://gist.github.com/orb/5884956

@theronic
Copy link

theronic commented May 1, 2017

Dead link: http://dosync.posterous.com/friendlier-shorter. Posterous Spaces are no longer available. Has this been republished elsewhere?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment