Due: October 9 at the end of the day.
You can get the Hugs system, as described in the book. You can also use runhaskell (/usr/local/bin/runhaskell), installed login.cs.ecu.edu.
We discussed the fixed-point operator of λ-calculus. In a typed language such as Haskell it is not possible to define a fixed-point operator without making use of recursion, but you can define it with recursion as follows.
fix f = f(fix f)Using Hugs or runhaskell or any other Haskell implementation, define a function on integers whose fixed-point is the factorial function. Use fix to find a fixed point, and run that fixed point on each integer from 0 to 8 to show that it correctly computes factorials for those numbers. Call your program fix.hs.
Write and test a Haskell program that solves a Sudoku puzzle.
You can represent a two-dimensional list as a list of lists. Think of it as a list of the rows of the two-dimensional list. Write a function that computes the transpose of a two-dimensional list. That it, it takes a list of rows and gives you a list of columns.
For a Sudoku puzzle, you need to be able to look at 3x3 squares. Write two functions, one that converts a puzzle into a list of its 3x3 squares (so that each 3x3 square becomes a row) and another that converts back from a list of 3x3 squares to a list of rows. So these two functions are inverses of one another.
You can represent a puzzle as a two-dimensional list each of whose members is a list, representing the possible values that can occur in the given position. The solution to a Sudoku puzzle requires that each number from 1 to 9 occur in exactly one position in each row. A useful tactic for solving a Sudoku puzzle is to look at each row, and, for each singleton list (representing a known quantity), remove the member of that singleton list from all of the other positions in that row. Write a function that takes a partially solved puzzle and produces a (hopefully more solved) puzzle by performing this tactic once on each row.
A Sudoku puzzle also requires each number from 1 to 9 to occur in each column. Write a function that performs the same tactic as above on each column. (Just transpose, do rows, and transpose back.)
A Sudoku puzzle also requires each number from 1 to 9 to occur in each 3x3 square (in a standard grid of 9 3x3 squares). Write a function that performs the same tactic on squares.
Write a function that repeatedly does the above tactic on each row, column and square until either all of the sets are singleton or the puzzle does not change from one iteration to the next. It should produce the final list.
It is conceivable that somebody asks you to solve an unsolvable puzzle. Modify your function from the preceding step so that it also stops if any of the lists of possible values is empty. When it encounters such a situation, it should produce an empty list.
The tactic that we have used does not solve all puzzles. But if you end up with an unsolved (but possibly solvable) puzzle, you can finish the job by finding a nonsingleton list of possible values and trying each value for that one in turn. Write another function that just returns the puzzle as is if it either contains an empty list or contains only singleton lists, and that uses this idea otherwise to find a solution (or to say that there is no solution).
You can describe a puzzle by a list of strings (each 9 characters long) using a digit for a known value and a dash for an unknown value. Write a function that takes such a list strings and produces a puzzle where each digit is replaced by a singleton list and each dash is replaced by [1,2,3,4,5,6,7,8,9].
Ideally, the program would read in the puzzle and solve it. But we have not talked about reading things, so write the program so that it defines thePuzzle as the puzzle to solve, and solves that puzzle. (That means that, if you want to solve a different puzzle, you edit the definition of thePuzzle.)