Friday, March 7, 2014

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 gridi,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.

5 comments:

  1. Hello, Such A Nice Article. Great Share. Also, if You Are Looking for sofas reviews and Guides. then you can checkout here.
    https://sofareviewsguide.puzl.com/
    https://bestkidscouchreviews.blogspot.com/

    ReplyDelete
  2. Erotic Services in Kootenays
    Find babes of a escort agency waiting for you, to fulfil each and every one of your BDSM and femdom KOOTENAYS dominatrix fantasies. Treat yourself to the delicious companionship provided by one of the many women working as independent KOOTENAYS escorts or Paddington escorts among many others. Are you tired of finding the same women on Baker Street, or the good old same Kings Cross escorts? Check our website and discover women only advertising here and providing an escort service KOOTENAYS that will blow your mind.

    ReplyDelete
  3. This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post.hosted call center solutions

    ReplyDelete