TDA 452
DIT 142
HT 2017

Functional Programming 2017
Lab 3 Extra Assignment

Lab 3 — Extra Assignments

Just for fun. You can choose freely whether to do 0, 1 or more of these. Don't expect us to spend time grading these however. There are no perfect, pre-defined answers here.
X. Perhaps if we picked the blank in a smarter way, the solve function would go faster?

One idea is to always pick the blank spot where there are as few possibilities left. For example, if we have a row with one or two blank spots, it is probably a good idea to pick one of those blank spots, since it will limit the consecutive search most, and it will lead to search to a state with more digits filled in. (Such a way of changing a solving method is called a heuristic -- there is no absoluate guarantee that the search will go faster, but often it actually will.)

Does your solve function work faster now? Experiment with different heuristics (for example: only look at rows and columns, and not at 3x3 blocks), and see which one performs best. Can you solve some of the hard Sudokus now?

Do not forget to add appropriate properties that test your functions.

Y. The solving method we have used in this lab assignment is very basic, and in some sense naive. The best known methods to solve problems like Sudoku is to also include the notion of propagation. This is the way most humans actually solve a Sudoku.

A simple variant of propagation is the following. Suppose we have Sudoku with a row with precisely one blank, such as the 3rd row in the example below:

Our current solution would go and pick blanks, and start searching recursively, without making use of the fact that we already know the value of that blank (namely 7 in this case); all the other values have been used by the other cells in the row.

Implement a function

propagate :: Sudoku -> Sudoku
that, given a Sudoku, finds out which rows, columns, and 3x3 blocks only have one blank in them, and then fills those blanks with the only possibly remaining value. It repeats doing this until all rows, columns and 3x3 blocks are either completely filled up, or contain two holes or more.

Now, add this function at the appropriate place in your solve function. Does it work faster now?

For other, more powerful propagation, you can for example read the following webpage:

Or come up with your own propagation rules!

Do not forget to add appropriate properties that test your functions.

Z. Write a function that produces interesting Sudoku puzzles. For example, one could have a function
createSudoku :: IO ()
that every time we run it, would print a new, interesting Sudoku puzzle on the screen.

One can discuss what an interesting Sudoku puzzle is. Here are three properties that an interesting Sudoku puzzle must have:

Can you think of a way to define a function for generating an infinite supply of new Sudokus satisfying the above two properties? You should of course make use of the functions you already have.

Do not forget to add appropriate properties that test your functions.

Å. Generalize the Sudokus that are dealt with in this assignment to other dimensions, for example 4x4 Sudokus, or 4x3 Sudokus. Do all dimensions make sense? Make sure your solution works in general, for all possible dimensions that make sense.

For inspiration, look here: Monster Sudokus. Or here: xkcd comics :-)

Do not forget to add appropriate properties that test your functions.

Ä1. The type we use to represent sudokus,
 data Sudoku = Sudoku { rows::[[Maybe Int]] }
is too big, meaning that it permits values that are not proper sudoku puzzles. This is why we wrote the function isSudoku to check that a sudoku is well-formed.

We could instead take advantage of Haskell's type system and define a type that exactly captures the set of values we want to work with, making the function isSudoku superfluous (i.e. it would return True for all values in the type), and eliminating the possibility of writing buggy functions that return ill-formed sudokus.

There are two independent improvements we can make:

Implement one or both of these improvements. (For defining the type Digit, the things you have already learned in this course should be enough. Defining the type Nine a should also be possible with what you already know, but it might result in long and repetitive code, so it is perhaps not worth it…)

A note on efficiency. Changing the representation of sudoku puzzles can also improve efficiency. List are efficient when the elements are processed sequentially (with functions like map, filter and sum), but less efficient when we need to access individual elements at random positions, like in the functions (!!=) and update in assignments E2 and E3. In my own experiments, replacing [[Maybe Int]] with (Nine (Nine Digit)), where Nine a was implemented as a triple of triples, made my solver ~15 times faster. (Thomas Hallgren, December 2017)

Ä2. Using a more specific type to represent sudoku puzzles means that we can't reuse the type if we want to solve other variants of sudoku puzzles, like we did in asssigment Å. And if we use different types for different puzzle variants, the types prevent us from applying the same solver function to puzzles of differents variants, even though the solver function in principle can be reused unchanged.

However, to decouple the solver function from particular puzzle types, we can define a type class

class Puzzle p where
and generalize your solver to work for any type in this class:
solve :: Puzzle p => p -> Maybe p
For this to work, the functions on puzzles that are used in the solver need to be turned into methods in the class, e.g. functions like isOkay, blanks, candidates.

A limitation of type classes, as originally defined in Haskell and presented in this course, is that they allow only one type (the type parameter in the class) to vary between different instances, but the methods in the Puzzle class need to refer to more than one type that might vary between different puzzle variants:

One compromise, to keep things simple, is to stick with fixed types for digits and positions, varying only the type of puzzles themselves between instances, sacrificing some of type safety we obtained in Ä1.
  class Puzzle p where
    candidates :: p -> Pos -> [Int]

To obtain a better solution we will need to use some Haskell language extensions available in GHC. This goes beyond what is covered in the course, so you will have to search for information on how to use these extensions on your own. There are two possibilities:

Ö. We have stated the soundness of the solve function as a property; every produced solution should be a real solution. The dual of soundness is completeness. Completeness says that whenever there is a solution, the solve function should also produce a solution. (Equivalently, if the solve function says that there is no solution, then there really is no solution.)

If we define the following helper datatype:

data SolvableSudoku = Solvable Sudoku
Then, implement a property
prop_SolveComplete :: SolvableSudoku -> Bool
prop_SolveComplete (Solvable sud) = (...)
that states that, for any solvale Sudoku, solve produces an answer.

Now, make the type SolvableSudoku an instance of Arbitrary:

instance Arbitrary SolvableSudoku where
  arbitrary = (...)
Here, you need to think about how to generate arbitrary Sudokus that are guaranteed to be solvable!

One idea is to start with an arbitrary solved Sudoku, and randomly blank out some of the digits. Implement this!

Back to Lab 3 description