# Sudoku

## Fork this

## Fight!

First of all, we need to have a representation for sudoku boards. Here is one.

```
(board [[5 3 0 0 7 0 0 0 0]
[6 0 0 1 9 5 0 0 0]
[0 9 8 0 0 0 0 6 0]
[8 0 0 0 6 0 0 0 3]
[4 0 0 8 0 3 0 0 1]
[7 0 0 0 2 0 0 0 6]
[0 6 0 0 0 0 2 8 0]
[0 0 0 4 1 9 0 0 5]
[0 0 0 0 8 0 0 7 9]])
```

Here `0`

is used to encode an empty square in a sudoku board.

The `board`

function is intended to transform a nested vector structure to some internal representation. Since these nested vectors work just fine for now, `board`

doesn’t have to do anything.

The standard library defines a function called `identity`

that just returns its parameter:

```
(identity 13) ;=> 13
(identity ":)") ;=> ":)"
```

Using `identity`

, we can define `board`

easily:

`(def board identity)`

You’re going to need the set of numbers used in sudoku often, so let’s define them as a set:

`(def all-values #{1 2 3 4 5 6 7 8 9})`

In sudoku, one needs to fill a board so that every line, every column and every block has the numbers from 1 to 9 exactly once. Blocks are 3x3 areas inside the sudoku board.

```
;[[5 3 0 | 0 7 0 | 0 0 0]
; [6 0 0 | 1 9 5 | 0 0 0]
; [0 9 8 | 0 0 0 | 0 6 0]
; -------+-------+-------
; [8 0 0 | 0 6 0 | 0 0 3]
; [4 0 0 | 8 0 3 | 0 0 1]
; [7 0 0 | 0 2 0 | 0 0 6]
; -------+-------+-------
; [0 6 0 | 0 0 0 | 2 8 0]
; [0 0 0 | 4 1 9 | 0 0 5]
; [0 0 0 | 0 8 0 | 0 7 9]]
```

## Working with nested structures

Getting values from nested structures with `get`

gets ugly:

```
(get (get [["a" "b"] ["c" "d"]] 0) 1)
;=> (get ["a" "b"] 1)
;=> "b"
```

To remedy this, there is `(get-in nested-structure directives)`

```
(get-in [["a" "b"] ["c" "d"]] [0 1])
;=> (get (get [["a" "b"] ["c" "d"]] 0) 1)
;=> (get ["a" "b"] 1)
;=> "b"
```

It works with everything that supports get, including maps and vectors.

```
(def cities {:title "The City and the City"
:author {:name "China Miéville"
:birth-year 1972}})
(get-in cities [:author :name])
;=> (get (get cities :author) :name)
;=> (get {:name "China Miéville", :birth-year 1972} :name)
;=> "China Miéville"
```

There are two other functions for dealing with nested structures, `assoc-in`

and `update-in`

. We will talk about `assoc-in`

in a bit.

Here is an example sudoku board together with its solution:

```
(def sudoku-board
(board [[5 3 0 0 7 0 0 0 0]
[6 0 0 1 9 5 0 0 0]
[0 9 8 0 0 0 0 6 0]
[8 0 0 0 6 0 0 0 3]
[4 0 0 8 0 3 0 0 1]
[7 0 0 0 2 0 0 0 6]
[0 6 0 0 0 0 2 8 0]
[0 0 0 4 1 9 0 0 5]
[0 0 0 0 8 0 0 7 9]]))
(def solved-board
(board [[5 3 4 6 7 8 9 1 2]
[6 7 2 1 9 5 3 4 8]
[1 9 8 3 4 2 5 6 7]
[8 5 9 7 6 1 4 2 3]
[4 2 6 8 5 3 7 9 1]
[7 1 3 9 2 4 8 5 6]
[9 6 1 5 3 7 2 8 4]
[2 8 7 4 1 9 6 3 5]
[3 4 5 2 8 6 1 7 9]]))
```

### Exercise 1

Write the function `(value-at board coordinates)`

that returns the value at `coordinate`

in `board`

:

```
(value-at sudoku-board [0 1]) ;=> 3
(value-at sudoku-board [0 0]) ;=> 5
```

### Exercise 2

Write the function `(has-value? board coordinates)`

that returns `false`

if the square at `coordinates`

is empty (has `0`

), and otherwise `true`

.

```
(has-value? sudoku-board [0 0]) ;=> true
(has-value? sudoku-board [0 2]) ;=> false
```

Now we can check if square is empty. To figure out which numbers are valid for a square we need to know which are already taken. Let’s write a couple of functions to figure this out.

### Exercise 3

Write the function `(row-values board coordinates)`

that returns a set with all numbers on the row of the coordinates

Remember that you can use destructing inside the parameter vector to get the row.

```
(row-values sudoku-board [0 2]) ;=> #{0 5 3 7}
(row-values sudoku-board [3 2]) ;=> #{0 8 6 3}
```

### Exercise 4

Write the function `(col-values board coordinates)`

that returns a set with all numbers on the col of the coordinates

```
(col-values sudoku-board [0 2]) ;=> #{0 8}
(col-values sudoku-board [4 8]) ;=> #{3 1 6 0 5 9}
```

Finally, we need to figure out what numbers are inside the block of a square.

To make working with blocks a little easier, let’s take a small detour.

You can use `for`

to go through a sequence like with `map`

:

```
(for [number [1 2 3]]
(+ number 2))
;=> (3 4 5)
```

Here the name `number`

gets bound to each value of the sequence `[1 2 3]`

one by one. For each value, evaluate the body `(+ number 2)`

with it and collect the results into a sequence.

But you can give `for`

multiple bindings, and it will go through all combinations:

```
(for [name ["John" "Jane"]
number [1 2 3]]
(str name " " number))
;=> ("John 1" "John 2" "John 3" "Jane 1" "Jane 2" "Jane 3")
```

If you happen to be familiar with list comprehensions from some other language, `for`

is Clojures list comprehension form.

To make working with coordinates a bit easier, let’s write a function that returns a sequence of coordinate pairs.

### Exercise 5

Write the function `(coord-pairs coord-sequence)`

that returns all coordinate-pairs of the form `[row col]`

where `row`

is from `coord-sequence`

and `col`

is from `coord-sequence`

.

```
(coord-pairs [0 1]) ;=> [[0 0] [0 1]
; [1 0] [1 1]]
(coord-pairs [0 1 2]) ;=> [[0 0] [0 1] [0 2]
; [1 0] [1 1] [1 2]
; [2 0] [2 1] [2 2]]
```

### Exercise 6

Write the function `(block-values board coordinates)`

that returns a set with all numbers in the block of `coordinates`

.

You might want to write a helper function that returns the coordinates for the top left corner of the block.

```
(block-values sudoku-board [0 2]) ;=> #{0 5 3 6 8 9}
(block-values sudoku-board [4 5]) ;=> #{0 6 8 3 2}
```

The `clojure.set`

namespace has some useful functions for working with sets. `(clojure.set/union set1 set2 ...)`

returns a set containing all the elements of its arguments:

`(clojure.set/union #{1 2} #{2 3} #{7}) ;=> #{1 2 3 7}`

In the project file, `clojure.set`

is required with the shorthand `set`

, so you can also just write:

`(set/union #{1 2} #{2 3} #{7}) ;=> #{1 2 3 7}`

Another helpful set operation is `(set/difference set1 set2)`

, which returns a set with all elements of `set1`

except those that are also in `set2`

. Or put another way, removes all elements of `set2`

from `set1`

:

```
(set/difference #{1 2 3} #{1 3}) ;=> #{2}
(set/difference #{1 2 3} #{2 4 5}) ;=> #{1 3}
```

### Exercise 7

Write the function `(valid-values-for board coordinates)`

that returns a set with all valid numbers for the square at `coordinates`

.

If the square at `coordinates`

already has a value, `valid-values`

should return the empty set `#{}`

.

Remember that we already defined the set `all-values`

.

```
(valid-values-for sudoku-board [0 0]) ;=> #{}
(valid-values-for sudoku-board [0 2]) ;=> #{1 2 4})
```

Next, let’s write a function to figure out if a sudoku board is completely filled.

### Exercise 8

Write the function `(filled? board)`

which returns `true`

if there are no empty squares in `board`

, and otherwise `false`

.

It might help to write a helper function that returns all numbers of the board in a sequence.

Remember that `(contains? set element)`

can be used to check if `element`

is in `set`

.

```
(filled? sudoku-board) ;=> false
(filled? solved-board) ;=> true
```

Now that we can check if a board is full, it would be nice to know if the solution is valid.

A sudoku is valid if each row, each column and each block contains the numbers from 1 to 9 exactly once. Let’s write functions for checking each of these conditions.

To start, let’s write some functions to get the values for each row, column and block.

### Exercise 9

Write the function `(rows board)`

that returns a sequence of value sets for each row of `board`

. That is, the first set in `(rows board)`

is a set that has every element of the first row of `board`

as element and so on.

```
(rows sudoku-board) ;=> [#{5 3 0 7}
; #{6 0 1 9 5}
; #{0 9 8 6}
; #{8 0 6 3}
; #{4 0 8 3 1}
; #{7 0 2 6}
; #{0 6 2 8}
; #{0 4 1 9 5}
; #{0 8 7 9}]
(rows solved-board) ;=> [#{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}]
```

Write the function `(cols board)`

that returns the values of each column in `board`

as a sequence of sets.

```
(cols sudoku-board) ;=> [#{5 6 0 8 4 7}
; #{3 0 9 6}
; #{0 8}
; #{0 1 8 4}
; #{7 9 0 6 2 1 8}
; #{0 5 3 9}
; #{0 2}
; #{0 6 8 7}
; #{0 3 1 6 5 9}]
(cols solved-board) ;=> [#{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}]
```

### Exercise 10

Write the function `(blocks board)`

that returns the values of each block in `board`

as a sequence of sets.

```
(blocks sudoku-board) ;=> [#{5 3 0 6 9 8}
; #{0 7 1 9 5}
; #{0 6}
; #{8 0 4 7}
; #{0 6 8 3 2}
; #{0 3 1 6}
; #{0 6}
; #{0 4 1 9 8}
; #{2 8 0 5 7 9}]
(blocks solved-board) ;=> [#{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}
; #{1 2 3 4 5 6 7 8 9}])
```

Now we can get the values used in every row, column and block. Let’s write functions that check if every row, column and block is valid as per the rules of sudoku.

### Exercise 11

Write the function `(valid-rows? board)`

that returns `true`

if every row in `board`

is a valid filled row.

```
(valid-rows? solved-board) ;=> truthy
(valid-rows? invalid-board) ;=> falsey
```

Write the function `(valid-cols? board)`

that returns `true`

if every row in `board`

is a valid filled column.

```
(valid-cols? solved-board) ;=> truthy
(valid-cols? invalid-board) ;=> falsey
```

Write the function `(valid-blocks? board)`

that returns `true`

if every block in `board`

is a valid filled block.

```
(valid-blocks? solved-board) ;=> truthy
(valid-blocks? invalid-board) ;=> falsey
```

Finally, we can write a function that checks if the whole board is a valid solution.

### Exercise 12

Write the function `(valid-solution? board)`

that returns `true`

if `board`

is a valid solution to sudoku.

```
(valid-solution? solved-board) ;=> truthy
(valid-solution? invalid-board) ;=> falsey)
```

Now we can verify whether or not a solution is valid. However, if we want to actually solve a sudoku, we need to be able to modify a partial solution.

Earlier we saw how useful `get-in`

can be when indexing nested structures. Theres a similar function for changing nested structures, called `assoc-in`

. `(assoc-in nested-structure path new-value)`

changes the value pointed by `path`

, which is a sequence of keys. Here’s an example:

```
(assoc-in [[:a :b] [:c :d]] [1 0] :E)
;=> (assoc [[:a :b] [:c :d]] 1 (assoc (get [[:a :b] [:c :d]] 1) 0 :E))
;=> (assoc [[:a :b] [:c :d]] 1 (assoc [:c :d] 0 :E))
;=> (assoc [[:a :b] [:c :d]] 1 [:E :d])
;=> [[:a :b] [:E :d]]
```

Now we can write a function to change a single value in our representation of a sudoku.

### Exercise 13

Write the function `(set-value-at board coord new-value)`

that changes the value at `coord`

in `board`

to `new-value`

.

```
(def before-change
(board [[5 3 0 0 7 0 0 0 0]
[6 0 0 1 9 5 0 0 0]
[0 9 8 0 0 0 0 6 0]
[8 0 0 0 6 0 0 0 3]
[4 0 0 8 0 3 0 0 1]
[7 0 0 0 2 0 0 0 6]
[0 6 0 0 0 0 2 8 0]
[0 0 0 4 1 9 0 0 5]
[0 0 0 0 8 0 0 7 9]]))
(def after-change
(board [[5 3 0 0 7 0 0 0 0]
[6 0 0 1 9 5 0 0 0]
[0 4 8 0 0 0 0 6 0]
[8 0 0 0 6 0 0 0 3]
[4 0 0 8 0 3 0 0 1]
[7 0 0 0 2 0 0 0 6]
[0 6 0 0 0 0 2 8 0]
[0 0 0 4 1 9 0 0 5]
[0 0 0 0 8 0 0 7 9]]))
(set-value-at before-change [2 1] 4)
```

Now that we can change the board, the next obstacle is figuring out what to change. Now we need to find an empty point in the sudoku board.

### Exercise 14

Write the function`(find-empty-point board)`

that returns coordinates to an empty point (that is, in our representation has value \(0\)).
Okay, so now we can find an empty location and we also know what the valid values for that location are. What’s left is to try each one of those values in that location and trying to solve the rest. This is called backtracking search. You try one choice and recurse, if the recursive call didn’t find any solutions, try the next choice. If none of the choices return a valid solution, return `nil`

.

Let’s take a small detour and see an example of backtracking search.

### Subset Sum

Subset sum is a classic problem. Here’s how it goes. You are given:

- a set of numbers, like
`#{1 2 10 5 7}`

- and a number, say
`23`

and you want to know if there is some subset of the original set that sums up to the target. We’re going to solve this by brute force using a backtracking search.

Here’s one way to implement it:

```
(defn sum [a-seq]
(reduce + a-seq))
(defn subset-sum-helper [a-set current-set target]
(if (= (sum current-set) target)
[current-set]
(let [remaining (clojure.set/difference a-set current-set)]
(for [elem remaining
solution (subset-sum-helper a-set
(conj current-set elem)
target)]
solution))))
(defn subset-sum [a-set target]
(subset-sum-helper a-set #{} target))
```

So the main thing happens inside `subset-sum-helper`

. First of all, always check if we have found a valid solution. Here it’s checked with

```
(if (= (sum current-set) target)
[current-set]
```

If we have found a valid solution, return it in a vector (We’ll see soon why in a vector). Okay, so if we’re not done yet, what are our options? Well, we need to try adding some element of `a-set`

into `current-set`

and try again. What are the possible elements for this? They are those that are not yet in `current-set`

. Those are bound to the name `remaining`

here:

` (let [remaining (clojure.set/difference a-set current-set)]`

What’s left is to actually try calling `subset-sum-helper`

with each new set obtainable in this way:

```
(for [elem remaining
solution (subset-sum-helper a-set
(conj current-set elem)
target)]
solution))))
```

Here first `elem`

gets bound to the elements of `remaining`

one at a time. For each `elem`

, `solution`

gets bound to each element of the recursive call

```
solution (subset-sum-helper a-set
(conj current-set elem)
target)]
```

And this is the reason we returned a vector in the base case, so that we can use `for`

in this way. Finally, we return each such `solution`

in a sequence.

So let’s try this out:

```
(subset-sum #{1 3 4 10 9 23} 20)
;=> (#{1 9 10} #{1 9 10} #{1 9 10} #{1 9 10} #{1 9 10} #{1 9 10})
```

Okay, so the above example is not exactly optimal. It forms each set many times. Since we were only interested in one solution, however, we can just add `first`

to the call if the helper:

```
(defn subset-sum [a-set target]
(first (subset-sum-helper a-set #{} target)))
```

And due to the way Clojure uses laziness, this actually cuts the computation after a solution is found (well, to be exact, after 32 solutions have been found due to the way Clojure chunks lazy sequences).

### Solving Sudokus

It’s finally time to write the search for a solution to sudokus.

### Exercise 15

Write the function `(solve board)`

which takes a sudoku board as a parameter and returns a valid solution to the given sudoku.

` (solve sudoku-board) => solved-board`

Recap of backtracking:

- check if you are at the end
- if so, is the solution valid?
- if not, return an empty sequence
- otherwise return
`[solution]`

- if not
- select an empty location
- try solving with each valid value for that location