Please install the Glasgow Haskell Compiler, available at http://www.haskell.org/ghc/

Submission instructions:

Submit a single Haskell source file.

Answer a), b) and c) as comments in this file.

Submit d) as a Haskell program in that file.
The file should have a "main" function that exercises a test
of your algorithm.

---------------------------------------

Lazy evaluation can modularize backtracking algorithms in an elegant way.

Here is a solution to the 8-queens problem in Haskell using lazy evaluation:

boardSize = 8
queens 0 = [[]]
queens n = [ x : y | y <- queens (n-1), x <- [1..boardSize], safe x y 1]
safe x [] n = True
safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
main = print (queens 8)

Understand how this program works. What happened to the usual backtracking?
(you don't need to write this in your hand-in).
If you don't understand the syntax in the 3rd line, see here:
http://www.haskell.org/haskellwiki/List_comprehension


Compare it with a typical "eager" solution such as this one:
http://www.cs.princeton.edu/introcs/23recursion/Queens.java.html

What would you have to do in both version, respectively, to
a) compute only the first 5 solutions and then stop
b) compute the number of solutions
c) find all solutions where the queen in column 3 is at row 5
You do not need to describe the actual changes or implementations of a), b) and c).
It is sufficient to outline briefly what you would have to do in both versions.

Your main programming assigments are this:
d) Take an arbitrary backtracking algorithm (different from N-queens) of your choice and implement
it using lazy evaluation in Haskell.

e) Re-implement the 8-queens Haskell algorithm above in Scheme. Simulate the lazy evaluation
by using the observation that you can delay an evaluation by wrapping it in a 
lambda expression, and force the evaluation by applying this lambda expression.
For example, lazy evaluation for the Haskell function and application

(\a -> a+a) 55

can be simulated by

((lambda (a) (+ (a) (a))) (lambda () 42))

This technique is so common that Scheme provides two functions, "delay" and "force" for this
purpose. They differ from the technique above in that delayed expressions are cached and computed
at most once. You can also use these functions.

If you want, you can also try to implement the algorithm in FAE instead (you'd need to either
add a few primitives for list processing or encode them using higher-order functions) 
- but this is optional.