Description
[1] A3×3 grid containing all the integers 1 to 9 is called a magic square if every row, every column, and
both diagonals all add up to 15, as in:
Suppose that 3×3 grids are represented using the following types:
type Grid = Matrix Int
type Matrix a = [Row a]
type Row a = [a]
and that you are given functions
rows :: Matrix a -> [Row a]
cols :: Matrix a -> [Row a]
diags :: Matrix a -> [Row a]
that extract the rows, columns and diagonals from a matrix.
a) Define a function sort :: [Int] -> [Int] that sorts a list of integers into numeric order, using a sorting
method of your choice. [6 points]
b) Using sort, define a function isValid :: Grid -> Bool that decides if a grid is valid, in the sense that it
contains all the integers 1 to 9. [6 points]
c) Define a function isMagic :: Grid -> Bool that decides if a grid is magic, in the sense that all rows,
columns and diagonals sum to 15. [6 points]
d) Using the library function replicate :: Int -> a -> [a], define the matrix choices :: Matrix [Int] that
contains [1..9] in every cell. [6 points]
e) [6 points] Define a function cp :: [[a]] -> [[a]] that returns the Cartesian product of a list of lists, e.g. cp
[[1,2,3],[4,5,6]] should give:
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
f) Using cp, define a function collapse :: Matrix [a] -> [Matrix a] that collapses a matrix of choices into a
choice of matrices. [6 points]
g) Using your answers to the previous parts of this question, define the list magics :: [Grid] of all possible
magic squares of size 3×3. [6 points]
h) Submit a pdf file named hw3comment.pdf. In that file, describe how you can make your Sudoku
Puzzle solver more interactive and more efficient. Describe your plan for implementation ( you can
mention the Haskell packages for doing that). [8 points]
NB: This is an open-ended assignment. Feel free to use anything from Haskell to solve this problem. In
your comment, describe how you test your functions. Provide some examples. Also, you can think of it
as a Sudoku Puzzle Solver. You can also consider the option from taking the puzzle from the user, and
showing the result to user. Monads!!! This part is optional. Think about how you can solve a large
Sudoku puzzle more efficiently? Parallel Programming? If we wish you can try to write your code
following that approach too. But, again this is optional. Have fun!
