Solving Sudoku with Clojure core.logic

Recently I had some fun solving Sudoku using Clojure.core.logic. Afterwards figuring out that it would actually be the example on the Wiki, but hey fun non the less and my solution actually is very close to the Wiki one, especially after cleaning it up.

I find core.logic fascinating as it allows to express logic problems in a very straight forward fashion, and given I will not learn Prolog anytime soon, it get me to some understanding of the ideas.

Solving a puzzle like Sudoku basically breaks down towards the following steps:

  1. Break down the puzzle according to the rules, in case of Sudoku this means defining rows, columns and squares
  2. Defining the variables for the pieces to be computed, in my case this means replacing input zeros with core.logic lvars.
  3. Define the rules, in case of Sudoku there are only, constraint on the numbers to 1-9, constraint on rows, columns and squares to have each number show up only once.
(defn solve
  "Takes a sudoku as a vector, with all empty cells set to 0 and returns
  a solved sudoku as a vector.

  (solve
    [0 0 0 2 6 0 7 0 1
     6 8 0 0 7 0 0 9 0
     1 9 0 0 0 4 5 0 0
     8 2 0 1 0 0 0 4 0
     0 0 4 6 0 2 9 0 0
     0 5 0 0 0 3 0 2 8
     0 0 9 3 0 0 0 7 4
     0 4 0 0 5 0 0 3 6
     7 0 3 0 1 8 0 0 0])
  "
  [sudoku]
  (let [board (vec (map #(if (zero? %) (lvar) %) sudoku))
        rows (indexed-sub-board board row-indexes)
        cols (indexed-sub-board board column-indexes)
        squares (indexed-sub-board board square-indexes)]

    (first
     (run 1 [q]
       (== q board)
       ;; only 1 - 9 are allowed
       (everyg #(fd/in % (fd/interval 1 9)) board)

       ;; every number can appear only once per row
       (everyg fd/distinct rows)
       ;; every number can appear only once per column
       (everyg fd/distinct cols)
       ;; every number can appear only once per square
       (everyg fd/distinct squares)))))

Overall the whole solution ended up very straight forward, the only problem I faced was the very macro heavy definition of core.logic, making debugging not as straight forward and I ended up reading a log of library code to figure out how things were supposed to work. But I guess this also comes from my general lack of knowledge in this specific kind of programming, and therefore having to read up on very basic concepts along the way.

The full code is available on github.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.