Algorithms and Data Structure I
Coursework Assignment: Sudoku assignment
Algorithms and Data Structure I
The 9 tasks in this assignment make up the Sudoku coursework assignment. The tasks in this assignment consist,
in the main, of functions or lines of code to be written in pseudocode. Because your solutions should be written in
pseudocode, marks will not be deducted for small syntax errors as long as the pseudocode can be understood by
a human. Having said that, it is highly recommended that you use the pseudocode conventions given in this module.
There are 50 marks available in total for this assignment
Background: Sudoku and Pseudoku
A Sudoku puzzle consists of 9-by-9 grid of squares, some of them blank, some of them having integers from 1 to 9.
A typical Sudoku puzzle will then look something like this:
To solve this puzzle, all the squares must be filled with numbers from 1 to 9 such that the following are satisfied:
1. every row has all integers from 1 to 9 (with each appearing only once)
2. every column has all integers from 1 to 9 (with each appearing only once)
3. every 3-by-3 sub-grid, or block (with bold outlines around them going from top-left to bottom-right) has all
integers from 1 to 9
In this coursework, we won’t be generating and solving Sudoku puzzles exactly, but a simplified version of Sudoku
puzzles, which I will call Pseudoku puzzles – pronounced the same. In a Pseudoku puzzle, we now have a 4-by-4
grid of squares, some of them blank, some of them having integers from 1 to 4. A typical Pseudoku puzzle will look
like this:
Now to solve this puzzle, all the squares must be filled with numbers from 1 to 4 such that the following are satisfied:
1. every row has all integers from 1 to 4 (with each appearing only once)
2. every column has all integers from 1 to 4 (with each appearing only once)
3. every 2-by-2 sub-grid, or block (with bold outlines around them going from top-left to bottom-right) has all
integers from 1 to 4
These three conditions will be called the Pseudoku conditions. For the above Pseudoku puzzle, a solution is:
The goal of the whole Sudoku assignment is to produce an algorithm that can generate Pseudoku puzzles. It is
important to emphasise that a Pseudoku puzzle is specifically a 4-by-4 puzzle as above, and not 9-by-9, or any other
size. So when we refer to Pseudoku puzzles, we are specifically thinking of these 4-by-4 puzzles.
Generating Pseudoku puzzles
You are going to produce an algorithm that generates a Pseudoku puzzle. This algorithm starts with a vector of
four elements, with all the integers 1 to 4 in any particular order, e.g. 1,2,3,4 or 4,1,3,2. In addition to this vector,
the algorithm also starts with an integer n, which is going to be the number of blank spaces in the generated puzzle.
This whole process will be more modular, i.e. the algorithm will combine multiple, smaller algorithms.
The big picture of the algorithm is to construct a solved Pseudoku puzzle by duplicating the input vector
mentioned earlier. Then from the solved puzzle, the algorithm will remove numbers and replace them with blank
entries to give an unsolved puzzle. These are the main steps in the algorithm:
1. Get the input vector called row and number n
2. Create a vector of four elements called puzzle, where each element of puzzle is itself the vector row
3. Cyclically permute the elements in each element of puzzle so that puzzle satisfies the Pseudoku conditions
4. Remove elements in each element of puzzle to leave blank spaces, and complete the puzzle
Steps 1 and 2 in this algorithm will involve writing functions in pseudocode and vector operations. Step 3 will, in
addition to the tools in Steps 1 and 2, involve using queue operations and adapting the Linear Search algorithm.
Step 4 can involve writing a function in pseudocode, or by some other means.
In the following sections, there will be some introductory information to set out the problem that needs to be
solved, along with the statement of task.
The puzzle format
As mentioned earlier, we will start with a completed puzzle stored in a four-element vector called puzzle where
every element is itself a four-element vector, such as
Each row of the puzzle will correspond to an element of a vector, e.g. the first row of the Pseudoku puzzle will
be stored as a four-element vector, which itself is an element of a four-element vector. Therefore, this completed
Pseudoku puzzle is represented by the following vector:
We could make this vector by initiating a four-element vector, with each element being empty, and then assign a
vector to each element. Here is a snippet of the pseudocode for this process but for only the first row of the puzzle:
new Vector row(4)
row[1] ← 2
row[2] ← 4
row[3] ← 1
row[4] ← 3
new Vector puzzle(4)
puzzle[1]← row
The goal of the algorithm in this coursework is to generate an unsolved Pseudoku puzzle from a row of four numbers.
The first step in the process is to make all four elements of a four-element vector to be the same, and this element
will be a four-element vector. For example, given a four-element vector with the numbers 2, 4, 1, 3, we produce
the following vector:
Your first task is to write a function in pseudocode that will carry out this process.
Task 1: Complete the following function template:
function MakeVector(row)
new Vector puzzle(4)
…
end function
This function should take a four-element vector called row as an input parameter and return a vector of four elements
called puzzle: each element of puzzle should contain the four-element vector row. Complete this function.
[4 marks]
Cyclic permutation of row vectors
Consider the following vector:
This does not satisfy the Pseudoku conditions since in each column only one number appears. The algorithm for
generating Pseudoku puzzles will cyclically permute the elements in each row vector until the numbers in all the
rows satisfy the Pseudoku conditions. A cyclic permutation of each row will shift all values of the elements one place
to the left (or the right) with the value at the end going to the other end. For example, for the second element in
the vector above, if we cyclically permute all elements one place to the right we will have:
Given a four-element vector and an integer p between 0 and 3 (inclusive) we want to write a function to cyclically
permute the values in the vector by p elements to the right. An elegant way to do this is to use the queue abstract
data structure. All values in a vector will be enqueued to an empty queue, e.g. the first row vector in the vector
above will give the following queue:
To cyclically permute all values one place to the right we copy the value stored at the head into a variable called
store, dequeue the queue, and then enqueue the value stored in store to the queue. This process will then give the
following queue:
To cyclically permute the values we can just repeat this process of storing the head value, dequeueing and then
enqueueing the stored value multiple times. When we are finished this process we then just copy the values stored in
the queue to a vector and return this vector. The next task is to formalise this process into a function in pseudocode.
Task 2: Complete the following function template:
function PermuteVector(row, p)
new Queue q
…
end function
This function should take a four-element vector called row as an input parameter and return that vector but with
its values cyclically permuted by p elements to the right: p should be a number between 0 and 3 (inclusive). To be
able to get full marks you need to use the queue abstract data structure appropriately as outlined above.
[6 marks]
The function PermuteVector, once completed, will only cyclically permute one vector. The next task is to take
a vector puzzle of the form returned by the function MakeVector, and apply PermuteVector to each of the
elements of puzzle. That is, given vector puzzle and three numbers x, y and z, elements 1, 2 and 3 of puzzle will
be cyclically permuted x, y and z places to the right respectively.
Task 3: Complete the following function template:
function PermuteRow(puzzle, x, y, z)
…
end function
This function should take a four-element vector called puzzle, which will be of the form of the output of MakeVector as an input parameter, as well as three integers x, y and z. The function will return puzzle but with elements
puzzle[1], puzzle[2] and puzzle[3] cyclically permuted by x, y and z elements respectively to the right: x, y and
z should all be numbers between 0 and 3 (inclusive). To be able to get full marks you should call the function
PermuteVector appropriately. HINT: You do not need to loop over integers x, y and z.
[4 marks]
Checking the Pseudoku conditions
The next step in constructing the algorithm is to write methods to decide if the Pseudoku conditions are satisfied.
If we start with the output of the function MakeVector(row), then all of the row conditions are satisfied as
long as row is a four-element vector with the numbers 1 to 4 only appearing once. However, the column conditions
are not satisfied: only one number appears in each column (four times). The 2-by-2 sub-grid conditions are also
not satisfied: in each sub-grid only two numbers appear (twice). In this part of the coursework we will write four
functions: one function to check the conditions for a single column of puzzle; one function to check all columns;
and one function to check the conditions for all 2-by-2 sub-grids.
In order to test whether all numbers from 1 to 4 appear in a column, we will use the Linear Search Algorithm
repeatedly. That is, first we construct a vector out of the four values in a column, and then we check if all the
numbers from 1 to 4 appear in that vector. The relevant Linear Search Algorithm for an input vector and the value
item is written as:
function LinearSearch(vector, item)
for 1≤ i≤LENGTH[vector] do
if vector[i]=item then
return TRUE
end if
end for
return FALSE
end function
Task 4: Complete the following function template:
function CheckColumn(puzzle, j)
new Vector temp(4)
…
end function
This function should take a four-element vector called puzzle, which will be of the form of the output of MakeVector as an input parameter, as well an integer j that will be a number between 1 and 4 (inclusive). This function
should construct a four-element vector called temp: each element temp[j] will be the jth element value of each row
vector in puzzle. Once the vector is constructed, apply LinearSearch(temp, k) for each integer 1 ≤k≤ 4. If all
numbers k are found in temp then return TRUE, otherwise return FALSE. To be able to get full marks you should
call the function LinearSearch appropriately.
[6 marks]
Task 5: Complete the following function template:
function ColCheck(puzzle)
…
end function
This function should take a four-element vector called puzzle, which will be of the form of the output of MakeVector as an input parameter. This should return TRUE if and only if CheckColumn(puzzle, j) returns TRUE for
all j. To be able to get full marks you should call the function CheckColumn appropriately.
[4 marks]
The next set of conditions to check is to see if all integers from 1 to 4 appear in the 2-by-2 sub-grids. We need
a convenient way to refer to the sub-grids. We will use a coordinate system of (row,col) for the four-element
vector puzzle: row is the index of the element of puzzle that we care about, and col is the index of the element in
puzzle[row] that we care about. Consider the following vector:
The coordinates of the element in yellow are (3,2), for example. Using this coordinate system to refer to the 2-by-2
sub-grids, the top-left sub-grid will consist of the elements (1,1), (1,2), (2,1) and (2,2): the top-left element is at
(1,1) and the bottom-right is at (2,2). We can now use this system to describe the 2-by-2 sub-grids. This can be
done by just specifying the coordinates of the top-left element and the bottom-right elements of the 2-by-2 sub-grid,
which will be specified by coordinates (row1,col1) and (row2,col2) respectively.
Consider the following pseudocode:
function CheckGrids(puzzle)
for 0 ≤ i ≤ 1 do
for 0 ≤ j ≤ 1 do
if CheckGrid(puzzle, 1 + 2i, 1 + 2j, 2 + 2i, 2 + 2j) = FALSE then
return FALSE
end if
end for
end for
return TRUE
end function
This pseudocode will check if 2-by-2 sub-grids defined by the top-left and bottom-right coordinates (row1,col1) and
(row2,col2) respectively return FALSE if we call the function CheckGrid. This function should check whether all
four elements of a 2-by-2 sub-grid defined by (row1,col1) and (row2,col2) contain all integers from 1 to 4: it should
return TRUE if it so, and FALSE otherwise. In the next task, the goal is write the function called CheckGrid,
which will take the row and column coordinates of the top-left and bottom-right elements of a 2-by-2 sub-grid and
return a Boolean.
Task 6: Complete the following function template:
function CheckGrid(puzzle, row1, col1, row2, col2)
…
end function
This function will take the four-element vector puzzle and numbers puzzle, row1, col1, row2, col2 as arguments.
The numbers row1, col1 and row2, col2 define the top-left and bottom-right coordinates of a 2-by-2 subgrid respectively. The function, when completed, should return TRUE if all numbers from 1 to 4 are stored in this sub-grid,
and FALSE otherwise. You can assume all the functions in the previous tasks are completed and defined, and you
may call these functions.
[6 marks]
Putting everything together
We now have all the ingredients to generate a solved puzzle given a row vector called row. The next task will involve generating the initial four-element vector called puzzle from row using MakeVector(row), trying all cyclic
permutations (using PermuteRow(puzzle, x, y, z) for all combinations of x, y and z) to see if the returned vector
returns TRUE for both CheckGrids and ColCheck.
Task 7: Complete the following function template:
function MakeSolution(row)
…
end function
This function will take the four-element vector row as input, which is the same input for the function MakeVector. The function should return a solved Pseudoku puzzle such that all column and sub-grid Pseudoku conditions
are satisfied. The function will generate a vector using MakeVector(row), then try cyclic permutations on this
vector using PermuteRow(puzzle, x, y, z) until a set of permutations is found such that all Pseudoku conditions
are satisfied (checked using CheckGrids and ColCheck). To be able to get full marks you should call the
functions MakeVector, PermuteRow, CheckGrids and ColCheck.
[6 marks]
All of the methods above will just produce a solved Pseudoku puzzle. In order to produce a proper Pseudoku puzzle,
numbers will need to be removed from the output of MakeSolution and replaced with a blank character. To
complete the algorithm for generating Pseudoku puzzles, in addition to the input vector row, we have the integer
n, which will stipulate the number of blank entries in the final puzzle.
Task 8: Describe a method for setting values to be blank characters in the elements of the output of MakeSolution. You can describe the method in words, use pseudocode, or use a flowchart. The method should take
the number n as an input parameter and set n values to be blank characters. You do not need to go into great
detail as long as the method makes sense. Maximum word count for the whole task (excluding diagrams): 200 words.
[4 marks]
Analysing the algorithm
In the next task, the goal is to analyse the algorithm in this assignment. The algorithm to generate Pseudoku
puzzles outlined here might not produce all possibly valid Pseudoku puzzles. Remember that, generally speaking,
the algorithm works by cyclically permuting several rows of a vector until the Pseudoku conditions are satisfied. In
the next task you should aim to identify all of the weaknesses you can think of in this algorithm and propose how
you could amend the current algorithm or design a new one to overcome these weaknesses.
Task 9: Describe and very briefly explain the limitations of the algorithm in this assignment [4 marks]. Then
you should outline another algorithm, which could be a modification of the existing one, or something completely
new, that overcomes the limitations of the algorithm in this assignment [6 marks]. Maximum word count for the
whole task: 600 words.
[10 mark
