Week 10 (Algorithms)

An algorithm is a logical, stuctured set of instructions that you can give to a computer in order that it may complete some given task. Technically, everything we have done so far has been an algorithm. However, over the next two weeks we will be looking at developing more sophisticated algorithms, with the ultimate aim of building a program that can solve an arbitrary sudoku puzzle.

We will not be introducing any major new ideas. However, these next few exercises should help you to develop a good understanding of two of the most fundamental programming concepts: loops (such as for and while) and conditionals (if, else). The recent algorithms lecture can be found here.

Some of these exercises can be challenging, and you should think about them very carefully. It is highly advised that you plan by sketching out your solution first with pen-and-paper so that you fully understand the logical flow of your program before you start typing. It is also advised that you try solving the problems by hand first and carefully analyse your own thought process, so you can understand the logic of what you need to do before applying it.

You should also note that many of these exercises (both from this week and next) build upon each other. Programming is about knowing when to call as function as much as knowing how to write one, and you should not waste time re-writing code when you don't have to. Wherever possible, you should try to include calls to your previously written functions. Note also that you can include calls to functions from different cells, you do not have to copy and paste them each time you wish to use them (just make sure you run the cell containing the definition before the one that calls it).n**

Exercise 20: Line-sudokus

A line-sudoku is a very simplified version of a sudoku. It is simply a 1D array of numbers, $1-9$ , for example:

A = \begin{bmatrix} 4 & 3 & 1 & 9 & 6 & 7 & 2 & 5 & 8 \end{bmatrix}.

Suppose that some of the values were removed, leaving us with an incomplete line-sudoku. We will indicate the removed values by $0$ . For example, $A$ might become...

A^\prime = \begin{bmatrix} 4 & 3 & 0 & 9 & 0 & 7 & 2 & 5 & 8 \end{bmatrix}.

a) Plan and write a function, lineSudSolver1( $A$ ), that takes an incomplete line-sudoku as its argument, and returns the missing numbers.

Note: As with many algorithmic problems, there are a few different ways to approach this problem, and some will take longer to write than others.

b) Plan and write another function, lineSudSolver2( $A$ ), that returns a completed version of the line-sudoku, $A$ .

Hint: You may wish to call lineSudSolver1( $A$ ) from part a) within this function. Also, when there are more than one zeros, the solution will not be unique.

c) Test your functions for parts a) and b) with the following incomplete line-sudokus:

In [5]:

LS1 = [0, 9, 3, 8, 6, 1, 7, 2, 5]
LS2 = [0, 7, 6, 0, 2, 8, 0, 3, 4]
LS3 = [0, 0, 0, 0, 0, 0, 0, 0, 0]

The file longLineSud.txt contains a line-sudoku, of length $L$ . It contains all numbers from $1-L$ , but with a single element replace with 0.

d) Read in the file longLineSud.txt, find out what $L$ is, and find the missing number.

Exercise 21: Box-sudokus

A box-sudoku is a small 2D version of a line-sudoku. You can think of it as a single one of the "boxes" of a full sudoku. It is simply a $3\times 3$ arrangement of the numbers $1-9$ . An example would be:

B = \begin{bmatrix} 4 & 3 & 1 \\ 9 & 6 & 7 \\ 2 & 5 & 8 \end{bmatrix}.

Similarly, an incomplete box-sudoku might look like this:

B^\prime = \begin{bmatrix} 4 & 3 & 0 \\ 9 & 6 & 7 \\ 0 & 5 & 0 \end{bmatrix},

where again a $0$ has replaced a missing element.

a) Plan and write a function, boxSudSolver1( $B$ ) that takes an incomplete box-sudoku as its argument, and returns a list of the missing numbers

b) Plan and write a function, boxSudSolver2( $B$ ) that takes an incomplete box-sudoku as its argument, and returns the completed box-sudoku.

c) Test these with the following box-sudokus:

In [6]:

import numpy as np

BS1 = np.array(
[[5, 0, 4],
 [8, 7, 3],
 [9, 1, 6]])

BS2 = np.array(
[[8, 0, 9],
 [1, 0, 2],
 [0, 5, 4]])

BS3 = np.array(
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]])

Exercise 22: Simplified sudoku

A full-sized sudoku puzzle consists of a $9\times 9$ grid, divided into $3\times 3$ boxes, as so:

Each row, each column, and each box must contain exactly the numbers

1-9

. It is therefore important that we can identify which box a given cell belongs to.

Each cell on the board can be referenced by a pair of co-ordinates,

(x,y)

. The co-ordinate

x

measures along from the left (remember that python arrays start with an index of

0

), and the

y

co-ordinate measures down from the top. So the location

(1,2)

indicates the cell one along from the left and two down from the top, which in the above puzzle is filled in by the number

1

One way to solve a full sudoku involves looking at one cell at a time. One can then isolate the row/column/box containing that cell, and find the set of numbers that are not in that row/column/box, and identify any overlap between them.

a) Plan and write a function, row(board, $x$ , $y$ ), that takes 3 arguments. The variable board should be a $9\times 9$ numpy array representing a (incomplete) sudoku board, which $x$ and $y$ are co-ordinates. The function should return a list or numpy array containing all the row-wise candidates. That is, all the numbers that are not in the indicated cell's row

b) Plan and write a function, column(board, $x$ , $y$ ), that gives the column-wise candidates for a given cell.

c) Plan and write a function, box(board, $x$ , $y$ ), that gives the box-wise candidates for a given cell.

d) Test these functions on sudSimp below, for cells (0,1) and (7,7)

In [2]:

import numpy as np
sudSimp = np.array([
    [1, 0, 6,   4, 5, 9,   3, 8, 2],
    [0, 5, 0,   0, 0, 3,   9, 6, 1],
    [9, 0, 8,   1, 0, 6,   5, 0, 4],
       
    [7, 9, 0,   3, 4, 8,   0, 2, 5],
    [0, 2, 3,   6, 0, 7,   0, 0, 8],
    [6, 0, 0,   2, 0, 5,   1, 3, 7],
       
    [0, 0, 7,   5, 0, 0,   0, 4, 9],
    [8, 0, 9,   0, 6, 4,   2, 0, 3],
    [3, 4, 0,   9, 0, 2,   0, 1, 6]
])

Note: We have also supplied the function sudPrinter(sud) to help visualise your sudoku boards. It takes in a $9\times 9$ numpy array, and displays it in blocks of $3$ .

In [3]:

def sudPrinter(sud):
    print(sud[0,0:3],sud[0,3:6],sud[0,6:10])
    print(sud[1,0:3],sud[1,3:6],sud[1,6:10])
    print(sud[2,0:3],sud[2,3:6],sud[2,6:10])
    print('')
    print(sud[3,0:3],sud[3,3:6],sud[3,6:10])
    print(sud[4,0:3],sud[4,3:6],sud[4,6:10])
    print(sud[5,0:3],sud[5,3:6],sud[5,6:10])
    print('')
    print(sud[6,0:3],sud[6,3:6],sud[6,6:10])
    print(sud[7,0:3],sud[7,3:6],sud[7,6:10])
    print(sud[8,0:3],sud[8,3:6],sud[8,6:10])
    return

Week 11 (Algorithms 2)

Exercise 23

This week we will be building upon the work done last week in order to build a program that can solve a full sudoku puzzle. Recall that a sudoku should have each number from $1-9$ in each column, row, and box.

In a typical sudoku problem, you will be presented with a partially-filled board. You must then fill in the empty cells (again represented by $0$ ) one at time, until the entire board is filled. All sudoku problems have a unique solution. However, these are not always easy to find.

Sudoku puzzles can be divided into two categories: easy and hard. Easy problems are step-wise deterministic This means at any point, there is an empty cell on the board which can be filled with no ambiguity. Therefore, by searching through the cells on the board, you will always come across at least one for which there is only one number between $1$ and $9$ that is not contained within the union of its row, column, and box.

Hard sudoku problems still have a unique solution, however the next step to take is not always obvious. This is usually the case when presented with an initial board with many unfilled cells. These problems require a program that can explore all of the branching possibilities of numbers that can go in each cell. In this exercise we will only be considering easy sudokus.

You should plan and write a function sudSolver(sud) that takes in a $9\times 9$ numpy array representing an incomplete sudoku board as its input. It should output the completed sudoku board. Test it on the board sudFullTest given below.

In [53]:

import numpy as np
sudFullTest = np.array([
    [0, 0, 0,   3, 7, 0,   0, 5, 6],
    [5, 0, 0,   0, 1, 0,   9, 7, 0],
    [0, 6, 0,   9, 8, 0,   3, 4, 0],
    
    [0, 0, 7,   0, 0, 2,   0, 8, 0],
    [0, 0, 9,   0, 3, 0,   6, 0, 0],
    [0, 5, 0,   8, 0, 0,   2, 0, 0],
    
    [0, 7, 5,   0, 6, 9,   0, 2, 0],
    [0, 4, 8,   0, 2, 0,   0, 0, 5],
    [2, 9, 0,   0, 5, 8,   0, 0, 0]
])

Hints

It is highly recommended that you write additional functions to help you with this. One of the most important things to learn as a programmer is which tasks to turn into separate functions. You should write your code such that a each task is represented by a different function. For example, you could write a separate function, posSolver(sud,x,y), that takes in the current board, and a specific location as its inputs. It could then return the number which should go in that cell if it can determine it, or $0$ if it can not.
Remember that a cell should only be filled in if you can find a unique solution for it - i.e. there is one number and one number only that can go there. For easy sudokus, such a cell will always exist at some point on the board.
There are $3$ conditions that a number needs to satisfy before it can fill a cell - it should be absent from the cell's row, column, and box. Make sure the number fits all conditions, and not just one of them.
If you want to create a new copy of an array without editing the old one, you must use newArray = oldArray.copy(). If you use newArray = oldArray, then the new array will overwrite the old one.
Use the sudPrinter(sud) function from last week to view your boards.

Bonus (Warning, very difficult!)

This is only for anyone who completes the above exercises and feels very confident in their python abilities. Try to construct a program which can solve a hard sudoku. Remember that although the solution is unique, the next step to take is not. You need to explore one set of branching possibilities until you come to a point which has no more available moves, before trying a different option. Reading up on "backtracking" and "recursive functions" will be helpful here.

You will not receive any additional marks for completing this. However, it will look very good if you want to apply for computational summer projects!

You can test it on the hard sudoku below:

In [3]:

import numpy as np
hardSud = np.array([
    [7, 0, 0,   0, 0, 0,   0, 0, 5],
    [6, 0, 9,   0, 0, 0,   0, 3, 0],
    [0, 0, 0,   1, 6, 0,   0, 4, 9],
    
    [4, 0, 0,   0, 1, 8,   5, 0, 0],
    [0, 0, 0,   0, 0, 0,   0, 0, 0],
    [0, 0, 8,   7, 5, 0,   0, 0, 4],
    
    [8, 4, 0,   0, 2, 5,   0, 0, 0],
    [0, 3, 0,   0, 0, 0,   8, 0, 7],
    [1, 0, 0,   0, 0, 0,   0, 0, 6]
])