# 61A Homework 14

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

## Logic Interpreter

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

## Sudoku

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.

### Question 1

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.``````

### Question 2

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.``````

### Question 3

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.``````

### Question 4

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.``````

### Question 5

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)))``````