#lang CSU660/schlac

;; grab the church functionality from class
(use-church)

;; convenient rewrite for local bindings
(rewrite (with [x E1] E2) => ???)
;; tests
(test (->nat (with [x (* 2 4)] (+ x x))) => '16)
(test (->nat (with [x 3] (with [x (* x 3)] (+ x x)))) => '18)

;; diff : Nat Nat -> Nat
;; computes the difference between two numbers: |x-y|
(define/rec diff
  (lambda (x y)
    ???))
;; tests
(test (->nat (diff 0 0)) => '0)
(test (->nat (diff 3 3)) => '0)
(test (->nat (diff 2 4)) => '2)
(test (->nat (diff 4 2)) => '2)

;; = : Nat Nat -> Bool
;; comparison for natural numbers
???
;; tests
(test (->bool (= 0 0)))
(test (->bool (= 1 1)))
(test (->bool (= (* (* 2 3) 2) (* 3 4))))

;; append : (Listof A) (Listof A) -> (Listof A)
;; appends two lists
???
;; tests
(test (->listof ->nat (append null null)) => '())
(test (->listof ->nat (append null l123)) => '(1 2 3))
(test (->listof ->nat (append l123 null)) => '(1 2 3))
(test (->listof ->nat (append l123 l123)) => '(1 2 3 1 2 3))

;; append* : (Listof (Listof A)) -> (Listof A)
;; appends a list of lists
(define/rec append*
  (lambda (lists)
    ???))
;; tests
(test (->listof ->nat (append* null)) => '())
(test (->listof ->nat (append* (cons null null))) => '())
(test (->listof ->nat (append* (cons l123 (cons l123 null))))
      => '(1 2 3 1 2 3))

;; map : (A -> B) (Listof A) -> (Listof B)
;; maps a function over a list, returning a list of result values
???
;; tests
(test (->listof ->nat (map add1 null)) => '())
(test (->listof ->nat (map (+ 2) l123)) => '(3 4 5))
;; the `map' examples below are just for fun
(test (->listof ->bool
                (with [tf (cons #t (cons #f null))]
                  (append* (map (lambda (x) (map (and x) tf)) tf))))
      => '(#t #f #f #f))
;; this is doing the same, using the fact that `not' returns a
;; function with swapped arguments
(test (->listof ->bool
                (with [tf (cons #t (cons #f null))]
                  (append* (map (not map tf) (map and tf)))))
      => '(#t #f #f #f))
;; (map and tf) = (not map tf and), so abstract the (not map tf) part
(test (->listof ->bool
                (with [nmtf (not map (cons #t (cons #f null)))]
                  (append* (map nmtf (nmtf and)))))
      => '(#t #f #f #f))
;; finally, do this for both `and' and `or'
(test (->listof ->bool
                (with [nmtf (not map (cons #t (cons #f null)))]
                  (with [ao (cons and (cons or null))]
                    (append* (map nmtf (append* (map nmtf ao)))))))
      => '(#t #f #f #f #t #t #t #f))

;; filter : (A -> Bool) (Listof A) -> (Listof A)
;; filters a list according to a given predicate
???
;; tests
(test (->listof ->nat (filter (= 3) null)) => '())
(test (->listof ->nat (filter (= 3) l123)) => '(3))
(test (->listof ->nat (filter (lambda (x) (= 1 (diff x 2))) l123))
      => '(1 3))

;; From this point we start with the actual solution.  A configuration
;; of a board is a list of numbers: each number represents the column
;; of a queen at that row.  For example (0 1 0) represents three rows,
;; where the queen of the first row stands on the first column, the
;; second row queen is at the second column, and the third is on the
;; first column.

;; threaten? : Nat Nat Nat -> Bool
;; determines whether a queen at column x and a queen at column y are
;; threatening each other if they are n rows apart
(define threaten?
  (lambda (x y n)
    ??? ; hint: use (diff x y)
    ))
;; tests
;; if both are at column 1, then they always threaten each other
(test (->bool (threaten? 1 1 1)))
(test (->bool (threaten? 1 1 2)))
(test (->bool (threaten? 1 1 3)))
;; if the first is at 1 and the second at 3, then they threaten each
;; other if they are two rows apart
(test (->bool (not (threaten? 1 3 1))))
(test (->bool      (threaten? 1 3 2)))
(test (->bool (not (threaten? 1 3 3))))
;; same when the columns are swapped
(test (->bool (not (threaten? 3 1 1))))
(test (->bool      (threaten? 3 1 2)))
(test (->bool (not (threaten? 3 1 3))))

;; safe? : Nat Nat (Listof Nat) -> Bool
;; determines whether it's safe to put a queen at column col when its
;; n rows before a list of column positions cols; in other words,
;; (safe col 1 cols) determines if you can put a queen at column col
;; just before the configuration specified by cols; (this is a helper
;; for `rows' below)
(define/rec safe?
  (lambda (col n cols)
    (or (null? cols)
        ??? ; uses `threaten?', of course
        )))
;; tests
(test (->bool (safe? 5 1 l123)))

;; configurations : Nat (Listof Nat) -> (Listof (Listof Nat))
;; this is the core of the solution: finds all valid n-row
;; configurations where the columns can be in the given list of cols
(define/rec configurations
  (lambda (n cols)
    (if (zero? n)
      (cons null null)
      (append* (map (lambda (rest)
                      (map ???
                           (filter ??? ; uses `safe?'
                                   cols)))
                    (configurations (sub1 n) cols))))))
;; no need to test this, since the main `queens' function is a simple
;; call to this function

;; range : Nat Nat -> (Listof Nat)
;; returns the list of numbers starting from the first argument, up to
;; (but not including) the second argument
(define/rec range
  (lambda (from to)
    ???))
;; tests
(test (->listof ->nat (range 0 0)) => '())
(test (->listof ->nat (range 0 5)) => '(0 1 2 3 4))
(test (->listof ->nat (range 2 5)) => '(2 3 4))

;; queens : Nat -> (Listof Nat)
;; finally, the solution is simple -- find all the configurations of
;; `size' rows, where each row has a queen at some column 0 to `size',
;; and return the first one
(define queens
  (lambda (size)
    (car ???)))
;; tests
;; single solution for a 1x1 board:
(test (->listof ->nat (queens 1)) => '(0))
;; no solution for 2x2 or 3x3 boards
(test (->listof ->nat (queens 2)) => '())
(test (->listof ->nat (queens 3)) => '())
;; and finally test a few solution (note that these tests depend on
;; the specific algorithm since there are many correct solutions, so
;; they are *not* good tests)
(test (->listof ->nat (queens 4)) => '(2 0 3 1))
(test (->listof ->nat (queens 5)) => '(3 1 4 2 0))

;; 8 : Nat
;; define this so you can run the real problem conveniently
(define 8 (+ 4 4))
;; tests
(test (->nat 8) => '8)

;; Finally, this is what you want to try:
;;   (->listof ->nat (queens 8))
;; You can also try to see how long it takes to find all solutions by
;; making `queens' return the whole list, and use it like this:
;;   (->listof (->listof ->nat) (queens-all 4))