Introduction to Functional Programming -- Lab 3: "Sudoku" | TDA555 / DIT440, LP1, HT2010 | |||||||||||||||||||||||

Home | Schedule | Labs | Exercises | Exam | About | Fire | Forum | TimeEdit | Links | 2009 | |||||||||||||||||||||||

Some notes:
Good luck!
Lab Assignment 3 -- Sudoku In this Lab Assignment, you will design a Haskell program that will be able to solve Sudokus, a popular logical puzzle originating from Japan.
There are 6 regular assignments as part of this Lab: A, B, C, D, E, and F. The lab consists (again) of two parts.
Assignments A, B, and C form Part I of the lab, and need to be submitted
before
Assignments
D, E and F form Part II of the Lab, and need to be submitted
before There are also extra assignments X, Y, Z, P, and Q. You can choose freely whether to do one of these.
The final deadline for this lab is
Some assignments have hints. Often, these involve particular standard Haskell functions that you could use. Some of these functions are defined in modules that you have to import yourself explicitly. You can use the following resources to find more information about those functions: We encourage you to actually go and find information about the functions that are mentioned in the hints!Sudokus Sudoku is a logic puzzle, originally coming from Japan. In the Western world, it has caught on in popularity enormously over the last couple of years. Most newspapers now publish a Sudoku puzzle for the readers to solve every day. A Sudoku puzzle consists of a 9x9 grid. Some of the cells in the grid have digits (from 1 to 9), others are blank. The objective of the puzzle is to fill in the blank cells with digits from 1 to 9, in such a way that every row, every column and every 3x3 block has exactly one occurrence of each digit 1 to 9. Here is an example of a Sudoku puzzle:
And here is the solution:
In this lab assignment, you will write a Haskell program that can read in a Sudoku puzzle and solve it.
If you want to read more about Sudokus, here are a few links:
Modelling Sudokus
To implement a Sudoku-solving program, we need to come up with a way of
modelling Sudokus. A Sudoku is a matrix of digits or blanks. The natural way of
modelling a matrix is as a list of lists. The outer list represents all the
rows, and the elements of the list are the elements of each row. Digits or
blanks can be represented by using the Haskell Summing up, a natural way to represent Sudokus is using the following Haskell datatype: Since it is convenient to have a function that extracts the actual rows from the Sudoku, we say: rows :: Sudoku -> [[Maybe Int]] rows (Sudoku rs) = rsFor example, the above Sudoku puzzle has the following representation in Haskell: example :: Sudoku example = Sudoku [ [Just 3, Just 6, Nothing,Nothing,Just 7, Just 1, Just 2, Nothing,Nothing] , [Nothing,Just 5, Nothing,Nothing,Nothing,Nothing,Just 1, Just 8, Nothing] , [Nothing,Nothing,Just 9, Just 2, Nothing,Just 4, Just 7, Nothing,Nothing] , [Nothing,Nothing,Nothing,Nothing,Just 1, Just 3, Nothing,Just 2, Just 8] , [Just 4, Nothing,Nothing,Just 5, Nothing,Just 2, Nothing,Nothing,Just 9] , [Just 2, Just 7, Nothing,Just 4, Just 6, Nothing,Nothing,Nothing,Nothing] , [Nothing,Nothing,Just 5, Just 3, Nothing,Just 8, Just 9, Nothing,Nothing] , [Nothing,Just 8, Just 3, Nothing,Nothing,Nothing,Nothing,Just 6, Nothing] , [Nothing,Nothing,Just 7, Just 6, Just 9, Nothing,Nothing,Just 4, Just 3] ]Now, a number of assignments follows, which will lead you step-by-step towards an implementation of a Sudoku-solver. Some Basic Sudoku Functions To warm up, we start with a number of basic functions on Sudukos.
To implement the above, use list comprehensions! Also, the following standard Haskell functions might come in handy: replicate :: Int -> a -> [a] length :: [a] -> Int and :: [Bool] -> BoolTo help you get started, ahere is a file that you can use: Reading and Printing Sudokus Next, we need to have a way of representing Sudokus in a file. In that way, our program can read Sudokus from a file, and it is easy for us to create and store several Sudoku puzzles. The following is an example text-representation that we will use in this assignment. It actually represents the example above. 36..712.. .5....18. ..92.47.. ....13.28 4..5.2..9 27.46.... ..53.89.. .83....6. ..769..43There are 9 lines of text in this representation, each corresponding to a row. Each line contains 9 characters. A digit 1 -- 9 represents a filled cell, and a period (.) represents a blank cell.
To implement the above, you will need to be able to convert between characters
(type ord '0' will play a central role in all this. You can
also use the function digitToInt.
Here are some functions that might come in handy: chr :: Int -> Char ord :: Char -> Int digitToInt :: Char -> Int putStr :: String -> IO () putStrLn :: String -> IO () sequence_ :: [IO a] -> IO () readFile :: FilePath -> IO String lines :: String -> [String]Here are some example Sudoku-files that you can download and use: Generating Sudokus as Test Data Finally, we need to be able to test properties about the functions related to our Sudokus. In order to do so, QuickCheck needs to be able to generate arbitrary Sudokus.
Let us split this problem into a number of smaller problems. First, we need to
know how to generate arbitrary cell values (of type
Here are some functions that might come in handy: sample :: Gen a -> IO () choose :: Random a => (a,a) -> Gen a frequency :: [(Int,Gen a)] -> Gen a sequence :: [Gen a] -> Gen [a]You might want to take a look at the lecture notes and example code on test data generation. Rows, Columns, Blocks Now, we are going to think about what actually constitutes a valid solution of a Sudoku. There are three constraints that a valid solution has to forfill: This leads us to the definition of ablock; a block is either a row or
a column or a 3x3 block. A block therefore contains 9 cells:
We are going to define a function that checks if a Sudoku is not violating any of the above constraints, by checking that none of the blocks violate those constraints.
Here are some functions that might come in handy:
nub :: Eq a => [a] -> [a] transpose :: [[a]] -> [[a]] take :: Int -> [a] -> [a] drop :: Int -> [a] -> [a]Note that some of the above functions only appear when you import Data.List.
You might want to take a look at the exercises and answers on lists and list comprehensions. Positions and Finding Blanks We are getting closer to the final solving function. Let us start thinking about how such a function would work. Given a Sudoku, if there are no blanks left in the Sudoku, we are done. Otherwise, there is at least one blank cell that needs to be filled in somehow. We are going to write functions to find and manipulate such a blank cell.
It is quite natural to start to talk about We use positions as indicating first the row and then the column. For example, the position (3,5) denotes the 5th cell in the 3rd row. Note: It is common in programming languages to start counting at 0! Therefore, the position that indicates the upper left corner is (0,0), and the position indicating the lower right corner is (8,8).
There is a standard function
We usually use the standard function This, in combination with list comprehensions, should be very useful for this assignment! When testing a property that is polymorphic (meaning that it has type variables in its type), you need to add a type signature that picks an arbitrary type. For example, when testing properties for the function (!!=), which works for lists of any type, you have to fix the type when testing, for example lists of Integers. Do this by adding a type signature to your properties. Here are some more useful functions: head :: [a] -> a (!!) :: [a] -> Int -> a zip :: [a] -> [b] -> [(a,b)]You might want to take a look at the exercises and answers on lists and list comprehensions. Solving Sudokus Finally, we have all the bits in place to attack our main problem: Solving a given Sudoku. Our objective is to define a Haskell function solve :: Sudoku -> Maybe SudokuThe idea is as follows. If we have a Sudoku sud that we would like to solve, we
give it to the function solve. This will produce one of two results:
How should solve be implemented. Here is one idea. When we try to solve a
given Sudoku sud, there exist three cases:
**sud**violates some of the constraints (in other words: some of its blocks contain the same digit twice). In this case, the answer of**solve**must be**Nothing**.**sud**does not contain any blanks (in other words:**sud**is a solution!). In this case, the answer of**solve**must be**Just sud**.- Otherwise,
**sud**must contain at least one blank cell. In this case, we try to*recursively*solve**sud**9 times; each time we update the blank cell with a concrete digit from 1 to 9. The first recursive attempt that succeeds is our answer. If none of the recursive attempts succeed, we return**Nothing**.
All the work we did in the assignments A -- E should be used in order to implement
the function
To implement the third, recursive, case of
QuickChecking the property Here are some useful functions: fromJust :: Maybe a -> a listToMaybe :: [a] -> Maybe aYou might want to take a look at the function majorities defined in the
lecture and exercises.
Here is an example of an impossible Sudoku: Extra Assignments You can choose freely whether to do 0, 1 or more of these. Remember that you need to have done an extra assignment for 3 out of 4 labs in order to get bonus points towards the final exam. There are no perfect, pre-defined answers here, but try to show your thoughts and understanding in your answers.
These are not obligatory, but you will learn more if you do them!
Submission Submit your solutions using the Fire system. Your submission should consist of the following files: Before you submit your code, Clean It Up! Remember, submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code: Good Luck! |