Week 12: Exercises

1. Replace

Write a function

replace :: Eq a => a -> a -> [a] -> [a]

such that (replace x y zs) replaces all occurrences of x with y in the list zs. Put your function in a module Util so that it can easily be used from other Haskell code.

2. Random Elements

a) Write a function randomElem that chooses a random element from a list. Give it an appropriate type.

b) Write a function minBy that applies a function f to all elements of a list xs and returns the value x for which f(x) is minimal. If there is more than one such x, choose one at random. Give your function an appropriate type.

3. N Queens

Is it possible to place N queens on an N x N chessboard such that no two queens attack each other?

a) Write a program that can print a list of all possible solutions for a given N. Use an exhaustive search. For example:

$ runghc queens.hs 4
. . Q . 
Q . . . 
. . . Q 
. Q . . 

. Q . . 
. . . Q 
Q . . . 
. . Q . 

$

b) What is the largest value of N for which your program can find a solution within a few seconds?