# 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]`

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.

nice blog

ReplyDeleteandroid training in bangalore

ios training in bangalore

machine learning online training

useful blog

ReplyDeletepython interview questions

cognos interview questions

perl interview questions

vlsi interview questions

web api interview questions

msbi interview questions

laravel interview questions

ReplyDeleteaem interview questions

salesforce interview questions

oops abab interview questions

itil interview questions

informatica interview questions

extjs interview questions

sap bi interview questions

ReplyDeletehive interview questions

seo interview questions

as400 interview questions

wordpress interview questions

accounting interview questions

basic accounting and financial interview questions