# 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