Lab 7: Solving Sudoku

---

In this lab, we explore how reasoning, and figuring things out by trial-and-error, can be coded as an algorithm, and use it to solve Sudoku puzzles.

Sudoku: The search for a solution

The most well known form of a sudoku puzzle is a 9-by-9 grid in which the numbers 1-9 must be placed such that each row, column and 3-by-3 box contains exactly one of each of the 9 digits. A typical puzzle will initially have enough of the numbers filled in to ensure that the puzzle has exactly one solution.

Finding a solution to the puzzle is a constraint satisfaction problem, just like the n-queens problem described in the lecture. (This differs from the constrained optimisation problems also talked about in the lectures only in that there is no objective function: Any way of satisfying the constraints is equally good.)

To find the solution we must search through the state space (all possible sets of 81 numbers that satisfy the constraints, i.e. all valid sudoku puzzles), trying different options until we find one that works. One possible (but certainly not ideal) way to approach this problem is to search through the entire state space until you find one that matches the puzzle you have been given. Considering that the total number of valid sudoku puzzles is 6,670,903,752,021,072,936,960, you would hope that there was a better way to go about it.

Indeed, as you have seen in the lectures we can use certain search algorithms to narrow the state space considerably as we work towards finding the solution. In this assignment you will implement one (or two) of these search algorithms to create your very own sudoku solver.

Exercise 7.1 (60%)

Implement the backtracking (depth-first search) algorithm with forward checking to solve 4-by-4 sudoku puzzles. (The rules for 4-by-4 sudokus are the same for 9-by-9’s as described above, but you will only use the digits 1-4 and the box constraint applies to the four 2-by-2 boxes.)

Snap link: A project file with the framework for the assignment is available here.

You must implement the block.

To run your solver, select a sudoku using the block. Then run your Solve block, sit back and watch it solve the sudoku. To check that your finished sudoku is correct (satisfies all the constraints) you can run the block.

A number of helpful blocks are provided:

• : This block sets the element at (row) (column) of (sudoku) to the given (value). It also updates what is shown on the stage. If the cell already had a value, it will be replaced.

• : This block to reports the current value of the element at (row) (column) of (sudoku). If the element is not set, the block reports the same value as the “Null” block.

• : This block clears (removes) the element at (row) (column) in (sudoku), and also updates the drawing on the stage.

• : This block implements forward checking. It will check if setting the element at (row) (column) ti the given value in the current partially filled-in sudoku violates any constraints.

• : This block reports whether there is any unset element in the sudoku. It returns a list, whose first element is or . If the first element is true, then the next two are the row and column of one of the empty elements in the sudoku.

Extension to Exercise 7.1:

Each time that the algorithm commits to a choice (assignment of a value to a cell in the sudoku puzzle), this choice is has been been vetted by the forward checking procedure. But forward checking is not complete, and therefore sometimes gets it wrong: When this happens, the search algorithm will eventually have to undo this bad choice, and try another option. When this kind of “mistake” is discovered, we call it a backtrack.

Add to you implementation a variable that counts how many backtracks are made while solving each puzzle. (Hint: It is probably easiest to do this with a global variable. If you use a global variable, please name it backtracks, so that we know how to make your exported blocks work. Also, don’t forget to reset it to zero before you start a new search.) Can you determine which of the example puzzles are the most difficult, based on the number of backtracks needed to solve them?

Exercise 7.2 (40%)

The amount of search (backtracks) is influenced by, among other things, the choice of which empty cell is filled in next, and the choice of the order in which the possible values are tried (such as 1,2,3,4 or 4,3,2,1). The block provided simply returns the first unset element in the sudoku. Is there a smarter strategy?

A common rule-of-thumb for variable ordering is to pick the variable (cell) with the fewest options first. In the extreme case, if a cell has only value that passes the forward check, then we cannot make a “mistake” in choosing this value (if that value doesn’t lead to a solution, it’s because of some mistake we had already made earlier).

Change the “find empty element” block so that it checks all empty spaces, and returns (in the same form as before) the one that has the fewest options (values that pass the forward check). To improve the efficiency of your solver, you can make this block return the list of possible values for the chosen empty cell, in addition to the true/false flag and the coordinates of the cell. This saves your search from having to call the forward check again on each value. Remember, though, that it must still return a list containing only “false” if there is no empty cell left.

Extension to Exercise 7.2:

Assuming you did the extension to the first exercise, does the modified variable ordering change the number of backtracks needed to solve the example puzzles?

Assignment submission

Commenting: Good programming practice includes providing adequate and useful comments in your code. Please make sure that you use comments where it is motivated: that is, where you need to explain what is going on in your code.

As important as providing good comments is to not clutter the code with useless comments. In particular, we sometimes provides hints and explanations to you as comments in the project files. These comments do not help us understand (and mark) your code, so they should, in most cases, not be included in the blocks that you submit.

Submission: To submit your assignment, you must export blocks (as described on the lab 1 page). For this assignment, you need to export and submit two files: The first with the “Solve” block that you created for exercise 7.1, and the second with “Find empty element” block, and the “Solve” block if you have modified it, for exercise 7.2. (As usual, also export any other custom blocks you created that are used by those.)

Submit both files through wattle.

Always test before you submit! Make sure everything that should be included is indeed included!

Marking: There are no marks for the extension tasks.

Sources

Nine by Nine Sudoku Puzzle: Licensed under the terms of the GNU Free Documentation License version 1.2 or later.

http://en.wikipedia.org/wiki/File:Oceans_Sudoku17_Puzzle-39451.svg

30 March, 2016
1191 words

---

Written by

Rachael McNaughton Patrik Haslum Lexing Xie

---

Tags
labs