haskell 代写 Solve Sudoku Puzzles Programming Fundamentals

Programming Fundamentals

Teaching Computers to Solve Sudoku Puzzles

For this project, you will write a computer program in Haskell to solve Sudoku puzzles. This involves implementing helper functions, basic game rules, designing and coding strategies to find solution to a given Sudoku puzzle. This is a group assignment (group of 3).

1. Introduction

To those unfamiliar with Sudoku, it is a logic puzzle game that was originally introduced in the USA as Number Place, and later became popular in Japan as Nanpure or Sudoku (translated to only single numbers allowed). The reason for Sudoku’s international popularity is that it offers players relaxation and fun while enhancing their brain fitness, including improvement of memory and logical thinking ability.

The puzzle is presented in a board or grid (like tic-tac-toe or chess) of 9×9 squares
or cells, divided in to 9 boxes of 3×3 each. Some cells are pre-filled with numbers while the rest are left blank. Below you can find an example Sudoku
and its solution.

For a given grid, a cell could be empty or contain a single digit. A row consists of 9 cells from left to right, a column consists of 9 cells from top to bottom, and a box is a 3×3 mini grid evenly distributed across the board.

2. The Code Framework

To get started with this project, you need to go to the course page and obtain the source files (sudoku.zip) that implement the basic sudoku framework.

This project was originally built with Stack. It is recommended that you also use Stack to compile and run the project for any performance test (e.g. measure how long it takes to solve a set of sudokus). For any other functional tests (e.g. check whether a function works as intended), you can use the interpreter to run the relevant modules.

To solve a Sudoku, you need to fill in the blank cells with numbers ranging from 1 to 9. The only constraint to this is that each cell must contain a value that is unique to that row, column, and box. These rows, columns, and boxes are referred to as regions.

1

Programming Fundamentals
The project files are organized in a file folder structure typical to Stack projects.

•   Top level files are required for Stack to build your project. Stack will create a new folder .stack- work that contains your project executable file.
•   The app folder contains Main.hs file, which is the gateway to our project. You can add multiple “solvers” to your project there.
•   The src folder contains program logics, including DataDefinition.hs for data models and Sudoku.hs for other functions. Your task is to implement the undefined functions in Sudoku.hs, and if you attempt the extension for this project, you might need to add new data structure into DataDefinition.hs.
•   The examples folder contains example sudoku puzzles on which you can test your sudoku solvers. Additional tests will be provided by your tutors if necessary.
•   The test folder contains hspec test cases. You will not need to implement test functions though your tutors may show you some test cases we use to test/mark your code.

  2.1.Compile, run and test your code

  Required packages

  This project makes use of a number of packages that are not part of the standard Haskell Prelude: clock, formatting and haddock. Simply run the following cabal commands in the terminal to install them:

  cabal install clock
  

  cabal install formatting
  

  cabal install haddock
  

  cabal install hspec
  

  Compile and run your project

  Compile your project using Stack will generate an executable file. You will notice that running this executable will return results much faster than the interpreter.

  In the terminal, navigate to the project folder and run the following commands to compile your project:

  stack setup
  stack build
  The .stack-work folder will be created by Stack. To run the project (i.e. the executable file), use: stack exec sudoku-exe — 1 examples/easy.txt

  Not surprisingly, the project fails to run at this stage, since you have not implemented the required functions yet. But let’s try to understand the above command. The arguments after double dash are not passed to stack, but required by the program itself (Main.hs). The argument 1 indicates that the first solver will be used to solve the sudokus found in the text file which is in fact the second argument, examples/easy.txt.

2

Programming Fundamentals

Test your project using the interpreter

If you want to quickly test a function in your project (before it is fully completed), instead of compiling the entire project using Stack, you could use the interpreter GHCi. For example, you can call the function printSudoku in src/Sodoku.hs by simply opening up WinGHCi ang dragging the source file and dropping it into the interface. This way, the source file will be loaded and you can simply call the function directly in WinGHCi.

Alternatively, you can also use the command ghci in the terminal, navigate to the src folder and load the file as follows:

To test the Main.hs file in the interpreter, you should first copy it to the src folder, then pass arguments to the main function using :main command:

3

Programming Fundamentals

3. Programming Tasks

This project requires you to implement a series of small helper functions, leading up to the most challenging one, the solve function.

To implement a Sudoku-solving program, the first question is how are we going to represent the puzzle to a machine? In this project, a Sudoku is represented as a grid or matrix of digits or blank cells. In Haskell, this can be modeled as a list of lists. The outer list contains rows, each of which is a list of cells and is a row itself. A cell can implemented using the type Maybe Int with Nothing represents a blank cell and Just x represents a cell with a digit from 1 to 9.

type Grid a = [Row a]
type Row a = [a]
type Cell = Maybe Int
data Sudoku = Sudoku (Grid Cell)

  deriving (Show, Eq)

3.1.Basic game rules and helper functions

Warming up

Hint: You can use in your code list comprehension here, or other standard functions including replicate, length, all, any.

T01. Implement a function sudokuAllBlanks :: Sudoku

This function creates a Sudoku containing only blank cells. Do not use copy-and-paste approach. You can instead define such a sudoku in as little as a single line, or at most a few short lines.

4

Programming Fundamentals

T02. Implement a function checkDimensions :: Sudoku -> Bool

While the types mentioned above represent a sudoku pretty well, they do not reinforce the rule of the game, i.e. there is nothing in the type definition that says a sudoku must have 9 rows and 9 columns. The functions checkDimentions will do just that, determine whether a given Sudoku has proper dimensions.

It is now the perfect time to introduce you to the doctest command that will do you a huge favour, testing your function! Pay attention to the comments above this function in the source file, they are no ordinary comments. In fact, the comments are embedded test cases that can be run against your implementation. They essentially say, if you run the code after the “>>>” sign on GHCi, your output should match the values right below. You can actually do so manually, or simply run the following command in the src folder for automated testing:

doctest Sudoku.hs

Before implementing this function, you might get some output like Examples: 15 Tried: 7 Errors: 0 Failures: 7, indicating that you have not passed any test case embedded in the file yet. These errors will go away once you provide correct implementation for the functions required.

T03. Implement a function checkNoBlanks :: Sudoku -> Bool

Your ultimate task is to solve Sudoku puzzle, so it would be nice to know when a Sudoku has no more blank cells to be filled. This function does not check whether the given sudoku is a valid solution. As long as the sudoku has no more blank cell blanks left, this function should return True.

Reading and printing Sudoku puzzles

In the text files under the examples folder, you will find sample sudoku puzzles. To make storing and retrieving puzzles in text files easy, we represent sudoku puzzles as an 81-character string of non-zero digits and non-digits. Non- digit characters (dot character) denote blank cells.

T04. Implement a function printSudoku :: Sudoku -> IO ()

This function prints a Sudoku on the screen in a more readable format. You can display the Sudoku in a basic format, or as a bonus (more details later), implement a prettier version of the printing function. The prettyPrintSudoku function should divide the grid into 3×3 mini-grids.

T05. Implement functions fromString and toString

fromString :: String -> Sudoku
toString :: Sudoku -> String

5

Programming Fundamentals

These functions convert an 81-character coded sudoku (of type String) into a Sudoku data structure, and vice versa. You can decide for yourself what to do if the string does not properly represent a sudoku.

Hint: Check out the functions chr, ord and digitToInt and the constant ord ‘0’. You need to be able to convert between characters (type Char) and digits (type Int).

Rows, Columns, Boxes and Regions

The only rule that you need to adhere when solving a sudoku is that no row, column or box (3×3 mini- grid) can contain the same digit twice. For your convenience, we define a type Region that could be either a row, a column or a 3×3 box. Every region therefore contains 9 cells:

type Region a = [a]
Hint: some functions that you might to use: nub, transpose, drop, take.

T06. Implement a function checkOkRegion :: Region Cell -> Bool This function checks whether a given region complies with the rule mentioned above.

T07. Implement functions getRows, getCols, getBoxs, getGrid getRows :: Grid a -> [Region a]
getCols :: Grid a -> [Region a]
getBoxs :: Grid a -> [Region a]

getGrid :: Sudoku -> Grid Cell

These functions extract the regions from a given grid, and a grid from a given sudoku.

T08. Implement a function prop_Sudoku :: Sudoku -> Bool

This function is required for the embedded test to work (it is essentially a QuickCheck property that is called by doctest). It checks whether a given Sudoku has 9 rows, 9 columns, 9 boxes and each region has exactly 9 cells.

T09. Implement a function checkOkSudoku :: Sudoku -> Bool
This function checks validity of a Sudoku as a whole, i.e. has proper dimensions, no region contains the

same digit twice.

Navigate around Sudoku grid

Hint: lists in Haskell are indexed from 0. To obtain an element at index i in a list, use the syntax list!!i

Each cell in the grid can be located by a pair of number (x,y) where x and y denote the row and column number of that cell respectively. The top left position is 0,0) and the bottom right is (8,8). Such position notation can be modelled as:

type Pos = (Int, Int)

6

Programming Fundamentals

T10. Implement a function nextBlankPos :: Sudoku -> Pos
This function, given a Sudooku that has not been solved, returns a position of a blank cell. It does not

matter (at this stage) which cell your pick to return.

T11. Implement a function (!!=) :: [a] -> (Int, a) -> [a]

This function inserts a value into a list at a specific index. In particular, it takes a list and a tuple containing an index in the list, and a new value. It then returns a new list with the new value assigned to the given index and all other values remain unchanged.

T12. Implement a function updateSudoku :: Sudoku -> Pos -> Int -> Sudoku This function updates a given Sudoku with a new cell value at a given position.

3.2.Solving Sudoku

You now should have all the tools necessary for completing the main task: solving a sudoku.

T13. Implement a function solve :: String -> [String]

This function takes an 81-character string representing a sudoku, fills in all the blanks, and returns a list of all possible solution sudokus. This solution list could be empty, meaning there is no solution to given sudoku, or a non-empty list with at least one solution. This solution sudoku, of course, must be valid.

To help you get started, below is a standard workflow:

 Check if a given sudoku violates any constraints. If it does, then you can return an empty solution list, i.e. it is not possible to solve the given puzzle.

 If the sudoku is valid and contains no blank cell, it is indeed a solution itself! In this case, simply return the sudoku’s string representation.

 Ifthesudokuisvalidandcontainsatleastoneblank,youcangetoneofthoseblanks(usingthe nextBlankPos function) and start filling it with some values.

One of the simplest (but least efficient) ways to go about filling a blank is to recursively try 9 times, each time update the blank with a digit from 1 to 9. There might be multiple values that succeed, i.e. do not cause the sudoku invalid. However, to simplify things, we can just choose the first legal value to be our answer (for now). You should consider to try out all other successful values later, as a sudoku can have multiple solutions.

This approach is known as brute force search or backtracking. It is not uncommon to realize down the track that a selection of value you made earlier, which was valid at the time, leads you to a dead end. That is, when you definitely want to go back, undo that selection and try out some other possible values. If you find your solver using this approach suboptimal or too slow when solving the harder puzzels, you will want to move on to more advanced techniques.

3.3. Documentation

It is a good practice in software development to document your code. This is to remind yourself why a function is implemented the way it is, and to help other people better understand your code. In this project, you are required to use a tool, haddock, for generating documentation from your annotated source code.

7

Programming Fundamentals
In your source file, you can annotate a function by putting some comment lines above the its definition.

The first comment line should be prefixed with — | and just — for the following lines: — | this function …
— more comment …
cell :: Gen (Maybe Int)

You could use multi-line comments using the syntax: {- ! … -}
These comments will be collected to produce HTML-based documentation for your source code.
After annotating your code, simply run the following command in the project folder to generate the doc. cabal haddock

HTML-based documentations will be produced and saved in the /dist/doc/html/sudoku folder. You should update the existing annotation in the provided code. For more advanced haddock format syntax, check out this page.

3.4.Extensions – more intelligent solvers

The abovementioned approach for solving Sudoku, namely brute force search, is easy to implement but can face with a huge search space. Suppose a given sudoku has 50 blank cells. Each of those 50 cells could have one of 9 possible values. With such a huge search space of 9^50 solutions, brute forcing can take billions of years to complete!

Human players, usually apply heuristics to guide their search of solutions. You are encouraged to explore different techniques and implement them in the program. This section explains some strategies to help you make your solver more intelligent.

If you have already implemented the backtracking solver, and want to create a new solver, you can leave the implemented solve function untouched, and create a new function with a different name, say, solve2. You can then register it in the main function, i.e. making a new solver_id.

(*) The documentation is created in the folder displayed in the above screenshot. Zip this folder as a zip

file for your final submission.

8

Programming Fundamentals

Extension 1

One way to boost performance of your solver is to make the nextBlankPos function smarter. At this stage, it just returns the blank cell it first encountered. What happens if it picks a blank that has the fewest candidate values? Will it help, and why? This improvement, in fact, narrows down the search space. You now have a smaller set of candidate values to work with. You should test your new solver with harder puzzles.

Extension 2

A popular approach used by humans for solving Sudoku is known as Constraint Propagation. Put simply, you simplify the puzzle every time you make a move. Let’s take a look at what experienced players normally do to solve their sudokus.

If you are playing Sudoku on paper, you might want to list all the possible values each cell could take, considering all regions around it. This way, we can narrow down the possible choices as well as to discover “already solved” cells (i.e., cells that could only take one specific value). The obvious thing to do now would be to solve the cells that have been narrowed to only one value. Then, you can eliminate those values from the neighbor cells (in same region). This act of updating the candidate values of the surrounding cells explains the name of this approach, that, you are updating (propagating) the candidate values (constraints) among neighbor regions, to bring it closer to the solution.

Other extensions

You can (and should) explore other techniques, like those discussed in Peter Norvig blog. One effective enhancement you can make is to look for pairs or triples within a region. You might find that a pair of cells has only two options of entries, but don’t know which goes where. What you can still gain from this observation is that those pair of numbers cannot occur anywhere else in the neighborhood. This will decrease the number of possibilities for the other cells in the neighborhood and help you get closer to a solution.

4. Submission details

Once you finish your program and generating documentation, submit two zip files as follows:

In the week after the submission, you will be asked to briefly demonstrate your code. This will be done on a random basis to make sure what submitted is your original work. Also, make sure to include any collaborations and/or relevant sources in the documentation.

Please check StudySmart for specific due date and link for assignment dropbox.

9

Programming Fundamentals

5. Marking criteria

To implement this project, you can make use of predefined functions that are part of the standard libraries (e.g. Data.List, Data.Maybe, ..). You are free to explore various functions in these libraries by searching for desired type signatures on https://www.haskell.org/hoogle/, or other resources on the Internet.

You should clean your code in order to receive full mark for each task. Code is considered clean if it:

 Does not have long lines (>75 characters) or tab characters.  Has a consistent layout.
 Has type signatures for all top-level functions.
 Has relevant comments.

 Has not junk (e.g. unused code, commented code, unnecessary comments)  Has no overly complicated functions
 Does not contain repetitive code

Below is the break down of this project mark. For the solve function, you need to run the executable file on a given test set (easy.txt and/or hard.txt). The total time it takes to solve a particular test set will be displayed at the end. This is the performance of your program that will be compared against the target. You should aim to satisfy the minimum performance requirement, i.e. your solve function should run faster than the target indicated in the marking guide.

All group members will receive the same project marks. If you have any issue working together

in the project, please inform your tutor as soon as possible.

10

Programming Fundamentals

6. Conclusion

We have developed this project using the declarative programming paradigm. We did not provide explicit step-by-step instructions. Instead, we are simply telling the machine: “Here are the rules about what you can and cannot do. Now go ahead and solve the puzzle”. If you implement it correctly, the program can then figure out what to do to achieve that goal.

* This project is based on an assignment in COMP1100, ANU 2017.

11