Haskell代写 | Assignment 3 COMP3400 Sudoku

这个作业是用Haskell实现一个快速的数独求解器
Assignment 3, COMP3400, Semester 1 2020
Sudoku
We’re going to implement a fast sudoku solver. For simplicity the version of
sudoku will be a bit different than the usual version which uses a 9×9 grid. We’re
instead going to use a 4×4 grid.
/–\/–\
|43||21|
|21||43|
\–/\–/
/–\/–\
|34||12|
|12||34|
\–/\–/
The rules of this sudoku are:
1. All rows must contain 1, 2, 3 and 4
2. All columns must contain 1, 2, 3 and 4
3. All disjoint 2×2 squares must contain 1, 2, 3 and 4
Constraint solving
To make the solver fast, we’re not going to do a brute force solution. Instead
we’re going to use logic programming!
Generation First we’ll generate constraints. Let’s focus on the rules for a
square:
/–\
|4X|
|2Y|
\–/
None of the numbers in a square can be duplicated, so we’ll generate the following
constraints:
• 2 is not 4
• X is not 4
• X is not 2
• Y is not 4
• Y is not 2
• Y is not X
Solving Then we’ll go through an instantiation phase. We’ll take the first
variable on the board (X) and instantiate it to 1, giving us these constraints:
• 2 is not 4
1
• 1 is not 4
• 1 is not 2
• Y is not 4
• Y is not 2
• Y is not 1
None of these are false yet so we can repeat: take the next variable on the board
(Y) and instantiate it to 1. The last constraint listed above fails. Next we’ll
try 2, which fails because of the second last constraint. Instantiating Y to 3
succeeds:
• 2 is not 4
• 1 is not 4
• 1 is not 2
• 3 is not 4
• 3 is not 2
• 3 is not 1
So we emit a solution for this square:
/–\
|41|
|23|
\–/
Finally for Y we try 4, which fails.
Since we’re finished with Y, we go back up and iterate on X. The next is X = 2,
which fails. X = 3 doesn’t fail so we try Y, which only succeeds when Y = 1:
/–\
|43|
|21|
\–/
Then X = 4, which fails. That’s all the solutions for the square.
This logic should be applied to all of the rules of the board. We’ll generate these
constraints for each cell in a row, each cell in a column and just like above, each
cell in a square.
Data Types and Functions
Data Types The first line in your solution must start with:
{-# LANGUAGE RankNTypes #-}
This enables an extension to Haskell. This extension allows us to write the type
of Logic:
data Logic a
= Logic (forall r. (a -> r -> r) -> r -> r)
2
We will also use the familiar State data type for the solution:
data State s a =
State (s -> (a, s))
To represent the game we’ll use:
data Digit
= D1
| D2
| D3
| D4
deriving (Eq, Ord, Show)
data Cell
= Unknown
| Known Digit
deriving (Eq, Ord, Show)
data Four a
= Four a a a a
deriving (Eq, Ord, Show)
data Board a
= Board (Four (Four a))
deriving (Eq, Ord, Show)
data Hole
= Concrete Digit
| Variable Int
deriving (Eq, Ord, Show)
data Constraint
= NotEqual Hole Hole
deriving (Eq, Ord, Show)
Visually the order of Four a b c d looks like:
/–\
|ab|
|cd|
\–/
Functions These functions make up the API:
— list of all sudoku rules applied to a board
generateConstraints :: Board Hole -> [Constraint]
— creates variables for unknown cells
3
cellToHole :: Cell -> State Int Hole
— replaces a variable in a board
substitute :: Int -> Digit -> Board Hole -> Board Hole
— replaces a variable in a constraint
instantiate :: Int -> Digit -> Constraint -> Constraint
— if no variables exist, emits the board
— otherwise solves the board’s next variable
solver :: [Constraint] -> Board Hole -> Logic (Board Digit)
— runs all of the above together
sudoku :: Board Cell -> Logic (Board Digit)
Instances
instance Functor Logic
instance Applicative Logic
instance Monad Logic
instance Functor (State s)
instance Applicative (State s)
instance Monad (State s)
instance Functor Four
instance Foldable Four
instance Traversable Four
instance Functor Board
instance Foldable Board
instance Traversable Board
Debugging
These are not required but you might find these useful for visualising boards:
prettyFour :: (a -> Char) -> Four a -> Four a -> String
prettyFour s (Four a b c d) (Four e f g h) =
unlines
[ “/–\\/–\\”
, “|” ++ [s a, s b] ++ “||”
++ [s e, s f] ++ “|”
, “|” ++ [s c, s d] ++ “||”
++ [s g, s h] ++ “|”
, “\\–/\\–/”
]
prettyBoard :: (a -> Char) -> Board a -> String
prettyBoard s (Board (Four a b c d)) =
prettyFour s a b ++ prettyFour s c d
4
Assessment
• This assignment contributes to 25% of the total marks for COMP3400.
• The marks for this assignment out of 25 will be distributed as follows:
– generateConstraints function 4 marks
– cellToHole function with 2 marks
– substitute function 2 marks
– instantiate function 2 marks
– solver function 5 marks
– sudoku function 2 marks
– Type-class instances 4 marks
– Overall design, including helpful program comments 4 marks
5