Sudoku in Loco

The Obligatory Sudoku Example

No discussion about constraint solvers is complete without the obligatory sudoku example. Unfortunately, sudoku is such a basic exercise for a constraint solver that it doesn’t really tell you much about the engine. But if anything, because sudoku is so standard, it has become a good way to get a feel for the style of the constraint DSL.

The Loco (0.2.0) version is concise and readable, with a nice separation between the core set of constraints that underlie all sudoku puzzles, versus the additional starter numbers provided by the puzzle.

In most constraint solvers, the constraint operators imperatively impose constraints on a variable store. In Loco, the constraint operators simply produce Clojure data structures. Since we’re working with Clojure data, assembling the full model is simply a matter of concatenating the sequence of constraints describing the fundamental rules of sudoku with the sequence of constraints specific to a given puzzle. This is a good example of how Loco lets you easily build portions of your model separately and then combine them or otherwise manipulate them with standard Clojure functions.

To follow the example, the main thing you need to know about Loco is that the notion of a subscripted variable, like $grid_{i,j}$, is represented in Loco as a vector, e.g., [:grid i j]

First, here’s how we’re going to ultimately input the Sudoku grids to our solver:

;http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-puzzle-ever-942299
(def worlds-hardest-puzzle
  [[8 - - - - - - - -]
   [- - 3 6 - - - - -]
   [- 7 - - 9 - 2 - -]
   [- 5 - - - 7 - - -]
   [- - - - 4 5 7 - -]
   [- - - 1 - - - 3 -]
   [- - 1 - - - - 6 8]
   [- - 8 5 - - - 1 -]
   [- 9 - - - - 4 - -]])

Here’s the solving code:

(def basic-model
  (concat
    ; range-constraints
    (for [i (range 9) j (range 9)] 
      ($in [:grid i j] 1 9)),
    ; row-constraints
    (for [i (range 9)]
      ($distinct (for [j (range 9)] [:grid i j]))),
    ; col-constraints
    (for [j (range 9)]
      ($distinct (for [i (range 9)] [:grid i j]))),
    ; section-constraints
    (for [section1 [[0 1 2] [3 4 5] [6 7 8]]
          section2 [[0 1 2] [3 4 5] [6 7 8]]]
      ($distinct (for [i section1, j section2] [:grid i j])))))

(defn solve-sudoku [grid]
  (solution
    (concat basic-model
            (for [i (range 9), j (range 9)
                  :let [hint (get-in grid [i j])]
                  :when (number? hint)]
              ($= [:grid i j] hint)))))

Let’s test it out in the REPL:

=> (solve-sudoku worlds-hardest-puzzle)
{[:grid 4 0] 3, [:grid 5 1] 8, [:grid 6 2] 1, [:grid 7 3] 5, 
 [:grid 8 4] 1, [:grid 3 0] 1, [:grid 4 1] 6, [:grid 5 2] 7, 
 [:grid 6 3] 9, [:grid 7 4] 2, [:grid 8 5] 8, [:grid 2 0] 6,
 [:grid 3 1] 5, [:grid 4 2] 9, [:grid 5 3] 1, [:grid 6 4] 7,
 [:grid 7 5] 6, [:grid 8 6] 4, [:grid 1 0] 9, [:grid 2 1] 7,
 [:grid 3 2] 4, [:grid 4 3] 8, [:grid 5 4] 6, [:grid 6 5] 4,
 [:grid 7 6] 9, [:grid 8 7] 5, [:grid 0 0] 8, [:grid 1 1] 4,
 [:grid 2 2] 5, [:grid 3 3] 2, [:grid 4 4] 4, [:grid 5 5] 9,
 [:grid 6 6] 3, [:grid 7 7] 1, [:grid 8 8] 2, [:grid 0 1] 1,
 [:grid 1 2] 3, [:grid 2 3] 4, [:grid 3 4] 3, [:grid 4 5] 5,
 [:grid 5 6] 5, [:grid 6 7] 6, [:grid 7 8] 7, [:grid 0 2] 2,
 [:grid 1 3] 6, [:grid 2 4] 9, [:grid 3 5] 7, [:grid 4 6] 7,
 [:grid 5 7] 3, [:grid 6 8] 8, [:grid 0 3] 7, [:grid 1 4] 8,
 [:grid 2 5] 1, [:grid 3 6] 8, [:grid 4 7] 2, [:grid 5 8] 4,
 [:grid 0 4] 5, [:grid 1 5] 2, [:grid 2 6] 2, [:grid 3 7] 9,
 [:grid 4 8] 1, [:grid 0 5] 3, [:grid 1 6] 1, [:grid 2 7] 8,
 [:grid 3 8] 6, [:grid 0 6] 6, [:grid 1 7] 7, [:grid 2 8] 3,
 [:grid 0 7] 4, [:grid 1 8] 5, [:grid 0 8] 9, [:grid 8 0] 7,
 [:grid 7 0] 4, [:grid 8 1] 9, [:grid 6 0] 5, [:grid 7 1] 3,
 [:grid 8 2] 6, [:grid 5 0] 2, [:grid 6 1] 2, [:grid 7 2] 8,
 [:grid 8 3] 3}

On my machine, this “hardest Sudoku” takes about 17ms to solve. Benchmarking against your favorite constraint solver on your machine, and pretty-printing the output as a readable grid are left as an exercise for the reader.