*Due by 11:59pm on Wednesday, 8/13*

**Readings:** You might find the following references
useful:

**Submission:** See the online submission
instructions. We have provided the following starter file:
hw14.logic

You should be using the same Logic interpreter that you used in lab. Instructions can be found in Lab 14. In particular, the tests can be run by:

`python3 logic.py -t hw14.logic`

Assume we have the two facts `insert`

and `anagram`

as follows:

```
(fact (insert ?a ?r (?a . ?r)))
(fact (insert ?a (?b . ?r) (?b . ?s))
(insert ?a ?r ?s))
(fact (anagram () ()))
(fact (anagram (?a . ?r) ?b)
(insert ?a ?s ?b)
(anagram ?r ?s))
```

Note that `anagram`

is just the `permutation`

fact from lecture
written in a slightly different way. With our `anagram`

fact, we can
write a few more facts to help us solve a 4 by 4 Sudoku puzzle! In
our version of Sudoku, our objective is to fill a 4x4 grid such that
each column, each row, and each 2 by 2 corner box of our simple grid
contain all of the digits from 1 to 4.

```
============
||A|A||B|B||
||A|A||B|B||
=====++=====
||C|C||D|D||
||C|C||D|D||
============
```

So in the puzzle above, the box containing A's should contain all the numbers from 1 to 4. The same applies to each of the boxes containing B's, C's and D's. In addition, each of the rows and columns must also contain all the numbers from 1 to 4.

Let's start by encoding the rule that each of the 2 by 2 boxes should
contain all the numbers from 1 to 4. Fill in the `boxes`

rule which
enforces this constraint. Note that the `boxes`

rule will *not* be
recursive.

```
(fact (boxes ((?a ?b ?c ?d)
(?e ?f ?g ?h)
(?i ?j ?k ?l)
(?m ?n ?o ?p)))
(anagram (?a ?b ?e ?f) (1 2 3 4))
; YOUR CODE HERE
)
(query (boxes ((?a 2 3 ?b)
( 3 4 1 2)
( 1 ?c 2 ?d)
( 4 2 3 1))))
; expect Success! ; a: 1 b: 4 c: 3 d: 4
(query (boxes ((?a 2 3 ?b)
( 3 4 3 2)
( 1 ?c 2 ?d)
( 4 2 3 1))))
; expect Failed.
```

Next, let's define a fact that specifies the rules for each row in our
grid. The input to `rows`

will be the entire 4x4 grid. The `rows`

fact should ensure that each row of the 4x4 grid is an `anagram`

of
`(1 2 3 4)`

. Fill in rest of the facts in the prompt below. Note
that the `rows`

fact should be recursive, unlike the `boxes`

fact
above.

```
(fact (rows ()))
(fact (rows (?x . ?xs))
; YOUR CODE HERE
)
(query (rows (( 1 2 4 ?a)
(?b 3 2 1)
(?c 4 3 2)
( 2 4 3 ?d))))
; expect Success! ; a: 3 b: 4 c: 1 d: 1
(query (rows (( 1 2 4 ?a)
(?b 3 2 1)
(?c 4 3 2)
( 3 4 3 ?d))))
; expect Failed.
```

Next, let's define the fact specifying the rules for each column in our
grid. Again, remember the the entire grid will be the input to
`cols`

. It should ensure that each column of the 4x4 grid is an
`anagram`

of `(1 2 3 4)`

.

```
(fact (cols (() () () ())))
; YOUR CODE HERE
(query (cols (( 1 ?b 4 ?d)
( 3 3 2 1)
(?a 1 ?c 2)
( 2 4 3 4))))
; expect Success! ; b: 2 d: 3 a: 4 c: 1
(query (cols (( 1 ?b 4 ?d)
( 3 3 2 1)
(?a 1 ?c 2)
( 2 4 3 1))))
; expect Failed.
```

Now, let's put all of this together to solve our any 4x4 Sudoku grid.
Since Logic is a declarative language, we only need to declare the
constraints on the Sudoku grid (which we have encoded in `boxes`

,
`rows`

, and `cols`

), and the Logic interpreter will automatically
search for the solution satisfying those constraints. Fill in the
fact below to complete the Sudoku solver.

```
(fact (solve ?grid)
; YOUR CODE HERE
)
(query (solve (( 1 ?b 4 ?d)
(?e 3 ?g 1)
(?i 4 ?k 2)
( 2 ?n 3 ?p))))
; expect Success! ; b: 2 d: 3 e: 4 g: 2 i: 3 k: 1 n: 1 p: 4
(query (solve (( 1 ?b 4 ?d)
(?e 3 ?g 1)
(?i 1 ?k 2)
( 2 ?n 3 ?p))))
; expect Failed.
```

**Note: This question is optional, and there is nothing to turn in.**

Solve the following sudoku puzzle with the new solver that you built! Notice that it is very slow.

```
;; MAKE SURE THAT THIS QUERY IS COMMENTED OUT BEFORE SUBMITTING
;; Otherwise you may time out the autograder.
;; (query (solve (( 3 ?b ?c 1)
;; ( 1 ?f ?g ?h)
;; (?i ?j ?k ?l)
;; (?m ?n 2 ?p))))
; YOUR CODE HERE
```

To improve upon the speed of our program, we notice that the main
thing we do is to check whether a set of four numbers is an anagram of
`(1 2 3 4)`

. So, we should optimize this call to be faster. One
possibility is to just describe all of the anagrams of `(1 2 3 4)`

to
Logic so that it doesn't have to figure it out itself. Uncomment the
lines that do this and run the query above again. It should be about
5 or 6 times as fast.

```
;; Solve the Sudoku puzzle below.
;; To solve the puzzle, uncomment the query below and run the file.
;; You may also want to comment out the other queries.
;; To run it with a different anagram fact, uncomment the relevant
;; facts below AND comment out all other anagram facts (including the
;; one at the beginning of this file).
;; Then quit any existing Logic interpreters, and reload the file.
;; Using the knowledge that we always want a permutation of (1 2 3 4)
;; (fact (member ?x (?x . ?r)))
;; (fact (member ?x (?y . ?r))
;; (member ?x ?r))
;; (fact (anagram (?a ?b ?c ?d) (1 2 3 4))
;; (member 1 (?a ?b ?c ?d))
;; (member 2 (?a ?b ?c ?d))
;; (member 3 (?a ?b ?c ?d))
;; (member 4 (?a ?b ?c ?d)))
;; Brute force - list all the possible anagrams
;; (fact (anagram (1 2 3 4) (1 2 3 4)))
;; (fact (anagram (1 2 4 3) (1 2 3 4)))
;; (fact (anagram (1 3 2 4) (1 2 3 4)))
;; (fact (anagram (1 3 4 2) (1 2 3 4)))
;; (fact (anagram (1 4 2 3) (1 2 3 4)))
;; (fact (anagram (1 4 3 2) (1 2 3 4)))
;; (fact (anagram (2 1 3 4) (1 2 3 4)))
;; (fact (anagram (2 1 4 3) (1 2 3 4)))
;; (fact (anagram (2 3 1 4) (1 2 3 4)))
;; (fact (anagram (2 3 4 1) (1 2 3 4)))
;; (fact (anagram (2 4 1 3) (1 2 3 4)))
;; (fact (anagram (2 4 3 1) (1 2 3 4)))
;; (fact (anagram (3 2 1 4) (1 2 3 4)))
;; (fact (anagram (3 2 4 1) (1 2 3 4)))
;; (fact (anagram (3 1 2 4) (1 2 3 4)))
;; (fact (anagram (3 1 4 2) (1 2 3 4)))
;; (fact (anagram (3 4 2 1) (1 2 3 4)))
;; (fact (anagram (3 4 1 2) (1 2 3 4)))
;; (fact (anagram (4 2 3 1) (1 2 3 4)))
;; (fact (anagram (4 2 1 3) (1 2 3 4)))
;; (fact (anagram (4 3 2 1) (1 2 3 4)))
;; (fact (anagram (4 3 1 2) (1 2 3 4)))
;; (fact (anagram (4 1 2 3) (1 2 3 4)))
;; (fact (anagram (4 1 3 2) (1 2 3 4)))
```