In Clojure, how can I check if a sudoku solution is valid?

Question

In an attempt to learn the basics of Clojure, I'm writing a Sudoku solution checker. I've stored the provided solution in a 2-d vector.

(def solution [[4 2 9 8 1 3 5 6 7]  
               [5 1 6 4 7 2 9 3 8] 
               [7 8 3 6 5 9 2 4 1] 
               [6 7 2 1 3 4 8 5 9] 
               [3 9 5 2 8 6 1 7 4] 
               [8 4 1 7 9 5 6 2 3] 
               [1 5 8 3 6 7 4 9 2] 
               [9 3 4 5 2 8 7 1 6] 
               [2 6 7 9 4 1 3 8 5]])

In Java, I could easily used nested loops to split up the horizontals, the verticals, and the squares, but I'm not sure how to approach this in Clojure.

My first attempt yielded something like this to get the sums of horizontals:

(def horizontals [])

(for [i solution] 
  (conj horizontals (reduce + i)))

Which printed out:

([45] [45] [45] [45] [45] [45] [45] [45] [45])

Is that the 'correct' way to check the horizontals? Or is there a better way in Clojure? How would I check the verticals or squares for their sums?

Answer 1

The horizontals are easy. It's literally just solutions: you want a list of lists of numbers, and that's what you already have!

I can't imagine why you want to sum things, since that's unrelated to checking a sudoku solution (which should involve checking for uniqueness). If you did, though, you could sum each horizontal with just (map #(reduce + %) solution).

The verticals involve a neat trick: you can use (apply map vector m) to transpose a "matrix" of nested vectors. So just turn the solution 90 degrees, and then check its horizontals! And of course if you want, you can add them up in the same way, although again I don't see why.

Squares are more interesting, and there are a few ways to go about it. I would use get-in and a sequence of coordinate pairs, like:

 (defn squares [solution]
   (for [y (range 3)
         x (range 3)]
     (for [y' (range 3)
           x' (range 3)]
       (get-in solution [(+ y' (* 3 y))
                         (+ x' (* 3 x))]))))

For completeness: I did say you should be checking for uniqueness rather than summing (after all, 9 5s sum to 45, but that's definitely not a good solution!). Here's one way you could verify that a list of 9 numbers constitute a valid row/column/square:

(defn valid? [numbers]
  (and (= 9 (count numbers)) 
       (= (set (range 1 10)) 
          (set numbers)))

Answer 2

While this isn't strictly an answer to the algorithm part of your question, I think it's worth pointing out that this code probably isn't doing what you think it's doing:

(def horizontals [])

(for [i solution] 
  (conj horizontals (reduce + i)))

You seem to expect for to be evaluated in an iterative fashion, and for each call to conj to update the contents of the var horizontals, appending the sum for each row to the vector. That is decidedly not how things operate in Clojure.

Rather, the empty vector [] is immutable; calling conj on the vector doesn't alter the contents of the vector -- it returns an entirely new vector that is the same as the original vector but with new element(s) added.

Similarly, calling (conj horizontals (reduce + i)) doesn't update the current value of horizontals. It's a function call that takes the current value of horizontals (a vector) and returns a new value (another, different vector); it's up to you to do something with that result. In general, once you def a variable, it remains unchanged throughout your program unless you explicitly change it. Programming by redefining vars is very much frowned upon in Clojure.

Finally, for isn't a looping construct in Clojure, it's a list comprehension. Essentially what it does is creates a lazy sequence consisting of the result of the inner expression (the conj function call) to a sequence of bindings that you provide (the [i solution] part). The expressions aren't actually executed until you consume the resulting lazy sequence -- in your case, by printing the results in the REPL.