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.logicAssume 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))
(anagram (?c ?d ?g ?h) (1 2 3 4))
(anagram (?i ?j ?m ?n) (1 2 3 4))
(anagram (?k ?l ?o ?p) (1 2 3 4)))
(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))
(anagram ?x (1 2 3 4))
(rows ?xs))
(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 (() () () ())))
(fact (cols ((?a . ?as) (?b . ?bs) (?c . ?cs) (?d . ?ds)))
(anagram (?a ?b ?c ?d) (1 2 3 4))
(cols (?as ?bs ?cs ?ds)))
(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)
(boxes ?grid)
(rows ?grid)
(cols ?grid))
(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))))
;; +-+-+-+-+
;; |3|2|4|1|
;; +-+-+-+-+
;; |1|4|3|2|
;; +-+-+-+-+
;; |2|3|1|4|
;; +-+-+-+-+
;; |4|1|2|3|
;; +-+-+-+-+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)))