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.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.
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:
36..712.. .5....18. ..92.47.. 596.13428 4..5.2..9 27.46.... ..53.89.. .83....6. ..769..43Our 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
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.propagate :: Sudoku -> Sudoku
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:
- sudoku.com, and click on "how to solve".
Do not forget to add appropriate properties that test your functions.
that every time we run it, would print a new, interesting Sudoku puzzle on the screen.createSudoku :: IO ()
One can discuss what an interesting Sudoku puzzle is. Here are three properties that an interesting Sudoku puzzle must have:
- There must be a solution
- There must not be two different solutions
- There must not be too many digits already visible
Do not forget to add appropriate properties that test your functions.
For inspiration, look here: Monster Sudokus. Or here: xkcd comics :-)
Do not forget to add appropriate properties that test your functions.
is too big, meaning that it permits values that are not proper sudoku puzzles. This is why we wrote the functiondata Sudoku = Sudoku { rows::[[Maybe Int]] }
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:
- Instead of using
Int
, we can define a typeDigit
that represents the digits 1 to 9, and nothing else. - Instead of using lists, we can define a type
Nine a
that represents vectors of size 9, together with safe indexing and updating functions that prevent index-out-of-bounds errors.
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)
However, to decouple the solver function from particular puzzle types, we can define a type class
and generalize your solver to work for any type in this class:class Puzzle p where
...
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 likesolve :: Puzzle p => p -> Maybe p
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:
- the type of the puzzles themselves,
- the type of the digits (or other symbols) that appear in the puzzle,
- and possibly the type of the positions (indexes) in the puzzle
(that we called
Pos
), but we could reuse the type for digits here.
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:
- use a multi-parameter type class, allowing
all the types that vary between instances to be parameters in the
type class. (You probably also need to specify
functional dependencies to avoid type ambiguities.)
class Puzzle p i d | p -> i d where candidates :: p -> i -> [d]
... - use type families, allowing type class definition to
specify types (in addition to functions), that can be defined in
different ways in different instances.
class Puzzle p where
typeIndex p
typeDigit p
candidates :: p -> Index p -> [Digit p]
...
If we define the following helper datatype:
Then, implement a propertydata SolvableSudoku = Solvable Sudoku
that states that, for any solvale Sudoku, solve produces an answer.prop_SolveComplete :: SolvableSudoku -> Bool prop_SolveComplete (Solvable sud) = (...)
Now, make the type SolvableSudoku an instance of Arbitrary:
Here, you need to think about how to generate arbitrary Sudokus that are guaranteed to be solvable!instance Arbitrary SolvableSudoku where arbitrary = (...)
One idea is to start with an arbitrary solved Sudoku, and randomly blank out some of the digits. Implement this!