Algorithms and Analysis COSC 1285 / COSC 2123
Assignment 2: Solving Sudoku
1 Objectives
There are three key objectives for this assignment:
• Apply transform-and-conquer strategies to to solve a real application.
• Study Sudoku and develop algorithms and data structures to solve Sudoku puzzles.
• Research and extend algorithmic solutions to Sudoku variants.
2 Learning Outcomes
This assignment assesses learning outcomes CLO 1, 2, 3 and 5 of the course. Please
refer to the course guide for the relevant learning outcomes: http://www1.rmit.edu.
au/courses/004302
3 Introduction and Background
Sudoku was a game first popularised in Japan in the 80s but dates back to the 18th
century and the “Latin Square” game. The aim of Sudoku is to place numbers from 1
to 9 in cells of a 9 by 9 grid, such that in each row, column and 3 by 3 block/box all
9 digits are present. Typical Sudoku puzzle will have some of the cells initially filled in
with digits and a well designed game will have one unique solution. In this assignment
you will implement algorithms that can solve puzzles of Sudoku and its variants.
Sudoku
Sudoku puzzles are typically played on a 9 by 9 grid, where each cell can be filled in
with discrete values from 1-9. Sudoku puzzles have some of these cells pre-filled with
values, and the aim is to fill in all the remaining cells with values that would form a valid
solution. A valid solution (for a 9 by 9 grid with values 1-9) needs to satisfy a number of
constraints:
1. Every cell is assigned a value between 1 to 9.
2. Every row contains 9 unique values from 1 to 9.
3. Every column contains 9 unique values from 1 to 9.
4. Every 3 by 3 block (called a box) contains 9 unique values from 1 to 9.
As an example, consider Figure 1. Figure 1a shows the initial Sudoku grid, with
some values pre-filled in. After filling in all the remaining cells with values that satisfy
the constraints, we obtain the solution illustrated in Figure 1b. As an exercise, check
that every row, column and 3 by 3 block/box (delimited by bold black lines) satisfy the
respective constraints.
(a) Puzzle. (b) Solved.
Figure 1: Example of a Sudoku puzzle from Wikipedia.
For further details about Sudoku, please visit https://en.wikipedia.org/wiki/
Sudoku.
Killer Sudoku
Killer Sudoku puzzles are typically played on 9 by 9 grids also and have many elements
of Sudoku puzzles, including all of its constraints. It additionally has cages, which are
subset of cells that have a total assigned to them. A valid Killer Sudoku must also satisfy
the constraint that the values assigned to a cage are unique and add up to the total.
Formally, a valid solution for a Killer Sudoku of 9 by 9 grid and 1-9 as values needs
to satisfy all of the following constraints (the first 4 are the same as standard Sudoku):
1. Every cell is assigned a value between 1 to 9.
2. Every row contains 9 unique values from 1 to 9.
3. Every column contains 9 unique values from 1 to 9.
4. Every 3 by 3 block/box contains 9 unique values from 1 to 9.
5. The sum of values in the cells of each cage must be equal to the cage target total
and all the values of in a cage must be unique.
2
As an example, consider Figure 2. Figure 2a shows the initial puzzle. Note the cages
are in different colours, and in the corner of each cage is the target total. Figure 2b is the
solution. Note all rows, columns and 3 by 3 blocks/boxes satisfy the Sudoku constraints,
as well as the values in each cage add up to the target totals.
(a) Puzzle. (b) Solved.
Figure 2: Example of a Killer Sudoku puzzle. Example comes from Wikipedia.
Sudoku Solvers
In this assignment, we will implement two families of algorithms to solve Sudoku, namely
backtracking and exact cover approaches. We describe these algorithms here.
Backtracking
The backtracking algorithm is an improvement on blind brute force generation of solu-
tions. It essentially makes a preliminary guess of the value of an empty cell, then try
to assign values to other unassigned cell. If at any stage we find an empty cell where it
is not possible to assign any values without breaking one or more of the constraints, we
backtrack to the previous cell and try another value. This is similar to a DFS when it
hits a deadend, if a certain branch of search tree results in an invalid (partial) Sudoku
grid, then we backtrack and another value is tried.
Exact Cover
To describe this, we first explain what is the exact cover problem.
Given a universe of items (values) and a set of item subsets, an exact cover is to select
some of the subsets such that the union of these subsets equals the universal of items (or
they cover all the items) and the subsets cannot have any overlapping items.
For example, if we had a universe of items {i1, i2, i3, i4, i5, i6}, and the following subsets
of items: {i1, i3}, {i2, i3, i4}, {i1, i5, i6}, {i2, i5} and {i6}, a possible set cover is to select
{i2, i3, i4} and {i1, i5, i6}, whose union includes all 6 possible items and they contain no
overlapping items.
The exact cover can be represented as a binary matrix, where we have columns (rep-
resenting the items) and rows, representing the subsets.
For example, using the example above, we can represent the exact cover problem as
follows:
3
i1 i2 i3 i4 i5 i6
{i1, i3} 1 0 1 0 0 0
{i2, i3, i4} 0 1 1 1 0 0
{i1, i5, i6} 1 0 0 0 1 1
{i2, i5} 0 1 0 0 1 0
{i6} 0 0 0 0 0 1
Using the above matrix representation, an exact cover is a selected subset of rows,
such that if we constructed a sub-matrix by taking all the selected rows and columns,
each column must contain a 1 in exactly one selected row.
For example, if we selected {i2, i3, i4} and {i1, i5, i6}, we have the resulting submatrix:
i1 i2 i3 i4 i5 i6
{i2, i3, i4} 0 1 1 1 0 0
{i1, i5, i6} 1 0 0 0 1 1
Note each column in this sub-matrix have a single 1, which corresponds to the re-
quirements of every item been covered and the subsets do not have overlapping items.
How does this relate to solving Sudoku puzzles? An example of transform and con-
quer, a Sudoku puzzle can be transformed into an exact cover problem and we can use
two exact cover algorithms to generally solve Sudoku faster than the basic backtracking
approach. We first describe the two algorithms to find exact cover, then explain how the
transformation works.
Algorithm X Algorithm X is Donald Knuth’s basic solution to the exact cover problem.
He devised Algorithm X to motivate the Dancing Links approach (we will discuss this
next). Algorithm X works on the binary matrix representation introduced previously.
Essentially it is a backtracking algorithm and works on the columns and rows of the
binary matrix. Recall that each column represents an item, and each row represents a
subset. What we want is to select some rows (subsets) such that across the selected rows,
there is exactly a single ’1’ in each of the columns – this condition means that all items are
covered and covered exactly once by the selected rows/subsets. We try different columns
and rows, and backtrack if there is an assignment that lead to an invalid (partial) grid.
After backtracking, another column/row will be selected.
Keeping this in mind, the algorithm goes through a number of steps, but aims to
essentially do what we have described above. See https://en.wikipedia.org/wiki/
Knuth%27s_Algorithm_X for further details.
Dancing Links Approach One of the issues with Algorithm X is the need to scan
through the (partial) matrices every time it seeks to select a column with smallest number
of 1’s, which row intersects with a column, and which column intersects with a row. Also
when backtracking it can be costly to reinsert rows and columns.
To address these challenges, Donald Knuth proposed a new approach, Dancing Links,
which is both a data structure and set of operations to speed up above.
The binary matrix for any exact cover problem is typically sparse (i.e., most entries
are 0). Recall our discussions about using linked list to represent graphs that are sparse,
i.e., few edges? We can do the same thing here, but instead use 2D doubly linked lists.
To best explain this, lets consider the structure from the exact cover example first:
4
Figure 3: Example of dancing links data structure. Note columns header nodes have
number of 1s in its column represented as [Y], where Y is the number of 1s. The structure
looks back on itself, in both columns and rows.
As we can see, there is a node for each ’1’ entry in the binary matrix. Each column
is a vertical (doubly) linked list, each row is a horizontal (doubly) linked list, and they
wrap around in both directions. In addition, each column has a header node, that also
lists the number of ’1’ entries, so we can quickly find the column with smallest number
of ’1’s.
To solve the exact cover problem, we would use the same approach as Algorithm X,
but now we can scan quickly and also backtrack more easily. The data structure only
has entries for ’1’s, so we can quickly scan through the doubly linked data structure
to analyse these. In addition, a linked list allows quick (re)insertion and deletion from
backtracking, which is one issue with the standard Algorithm X formulation. See https:
//arxiv.org/abs/cs/0011047 for further details.
Sudoku Transformation To represent Sudoku as an exact cover problem, we only
need to construct a relevant binary matrix representation whose exact cover solution
corresponds to a valid Sudoku assignment. At a high level, we want to represent the
constraints of Sudoku as the columns, and possible value assignments (the ‘subsets’) as
the rows. Let’s discuss the construction of the binary matrix first before explaining why
it works.
Rows:
We specify a possible value assignment to each cell as the rows. For a 9 by 9 Sudoku
puzzle, there are 9 by 9 cells, of which each can take 9 values, giving us 9 * 9 * 9 = 729
rows. E.g., (r = 0, c = 2, v = 3) is a row in the matrix, means assign value 3 to the cell
in row 0 column 2.
Columns: The columns represents the constraints. There are four kinds of constraints:
One value per cell constraint (Row-Column): Each each cell must contain exactly
one value. For a 9 by 9 Sudoku puzzle, we have 9 * 9 = 81 cells, and therefore,
we have 81 row-column constraints, one for each cell. If a cell contains a value
5
(regardless of what it is), we assign it a value of ’1’. This means for rows (r=0,
c=0, v=1), (r=0, c=0, v=2), ... (r=0, c=0, v=9) in the matrix, they will all have
’1’ in the column corresponding to the row-column constraint (r=0, c=0). This
construction will mean only one of the above is selected for (r=0, c=0), satisfying
this constraint. Same applies for the other cells.
Row constraint (Row-Value): Each row must contain each number exactly once. For
a 9 by 9 Sudoku puzzle, we have 9 rows and 9 possible values that can be assigned to
each row, i.e., 9*9=81 row-value pairs. Therefore, we have 81 row-value constraints,
one for each row-value pair. If a row contains a value (regardless in which column),
we assign it a value of ’1’. This means for rows (r=0, c=0, v=1), (r=0, c=1, v=1),
... (r=0, c=8, v=1) in the matrix, they will all have ’1’ in the matrix column
corresponding to the row-value constraint (r=0, v=1). This construction will mean
only one of the above matrix rows is selected in order to satisfy the row-value
constraint (r=0, v=1). Same applies for the other rows.
Column constraint (Column-Value): Each column must contain each number ex-
actly once. For a 9 by 9 Sudoku puzzle, we have 9 columns and 9 possible values
that can be assigned to each column, i.e., 9*9=81 column-value pairs. Therefore,
we have 81 column-value constraints, one for each column-value pair. If a column
contains a value (regardless in which row), we assign it a value of ’1’. This means
for rows (r=0, c=0, v=1), (r=1, c=0, v=1), ... (r=8, c=0, v=1) in the matrix, they
will all have ’1’ in the matrix column corresponding to the column-value constraint
(c=0, v=1). This construction will mean only one of the above rows is selected in
order to satisfy the column-value constraint (c=0, v=1). Same applies for the other
columns.
Box Constraint (Box-Value): Each box must contain each value exactly once. For a
9 by 9 Sudoku puzzle, we have 9 boxes and 9 possible values that can be assigned to
each box, i.e., 9*9=81 box-value pairs. Therefore, we have 81 box-value constraints,
one for each box-value pair. If a box contains a value (regardless in which cell of
the box), we assign it a value of ’1’. This means for rows (r=0, c=0, v=1), (r=0,
c=1, v=1), ... (r=2, c=2, v=1) in the matrix, they will all have ’1’ in the matrix
column corresponding to the box-value constraint (b=0, v=1). This construction
will mean only one of the above rows is selected in order to satisfy the box-value
constraint (b=0, v=1). Same applies for the other boxes.
Why this works? For exact cover, we select rows such that there is a single ’1’ in
all subsequent columns. The way we constructed the constraints, this is equivalent to
selecting value assignments (the rows) such that only value per cell, that each row and
column cannot have duplicate values, and each box also cannot have duplicate values. If
there are duplicates, then there will be more than a ’1’ in one of the column constraints.
By forcing to select a ’1’ in each column, we also ensure we a value is selected for every
cell, and all rows, columns and boxes have all values present.
This concludes the background. In the following, we will describe the tasks of this
assignment.
6
4 Tasks
The assignment is broken up into a number of tasks. Apart from Task A that should be
completed initially, all other tasks can be completed in an order you are more comfortable
with, but we have ordered them according to what we perceive to be their difficulty. Task
E is considered a high distinction task and hence we suggest to tackle this after you have
completed the other tasks.
Task A: Implement Sudoku Grid (4 marks)
Implement the grid representation, including reading in from file and outputting a solved
grid to an output file. Note we will use the output file to evaluate the correctness of your
implementations and algorithms.
A typically Sudoku puzzle is played on a 9 by 9 grid, but there are 4 by 4, 16 by 16,
25 by 25 and larger. In this task and subsequent tasks, your implementation should be
able to represent and solve Sudoku and variants of any valid sizes, e.g., 4 by 4 and above.
You won’t get a grid size that isn’t a perfect square, e.g., 7 by 7 is not a valid grid size,
and all puzzles will be square in shape.
In addition, the values/symbols of the puzzles may not be sequential digits, e.g., 1-9
for a 9 by 9 grid, but could be any set of 9 unique non-negative integer digits. The
same Sudoku rules and constraints still hold for non-standard set of values/symbols.
Your implementation should be able to read this in and handle any set of valid integer
values/symbols.
Task B: Implement Backtracking Solver for Sudoku (9 marks)
To help to understand the problem and the challenges involved, the first task is to develop
a backtracking approach to solve Sudoku puzzles.
Task C: Exact Cover Solver - Algorithm X (7 marks)
In this task, you will implement the first approaches to solve Sudoku as an exact cover
problem - Algorithm X.
Task D: Exact Cover Solver - Dancing Links (7 marks)
In this task, you will implement the second of two approaches to solve Sudoku as an exact
cover problem - the Dancing Links algorithm. We suggest to attempt to understand and
implement Algorithm X first, then the Dancing Links approach.
Task E: Killer Sudoku Solver (16 marks)
In this task, you will take what you have learnt from the first two tasks and devise
and implement 2 solvers for Killer Sudoku puzzles. One will be based on backtracking
and the other should be more efficient (in running time) than the backtracking one.
Your implementation will be assessed for its ability to solve Killer Sudoku puzzles of
various difficulties within reasonable time, as well as your proposed approach, which will
be detailed in a short (1-2 pages) report. We are as interested in your approach and
rationale behind it as much as the correctness and efficiency of your approach.
7
5 Details for all tasks
To help you get started and to provide a framework for testing, you are provided with
skeleton code that implements some of the mechanics of the Sudoku program. The main
class (RmitSudokuTester.java) implements functionality of Sudoku solving and parsing
parameters. The list of main java files provided are listed in Table 1.
file description
RmitSudokuTester.java Class implementing basic IO and processing code. Suggest
to not modify.
grid/SudokuGrid.java Abstract class for Sudoku grids Can add to, but don’t mod-
ify existing method interfaces.
grid/StdSudokuGrid.java Class for standard Sudoku grids. Please complete the im-
plementation.
grid/KillerSudokuGrid.java Class for Killer Sudoku grids. Please complete the imple-
mentation.
solver/SudokuSolver.java Abstract class for Sudoku solver algorithms. Can add to,
but don’t modify existing method interfaces.
solver/StdSudokuSolver.java Abstract class for standard Sudoku solver algorithms, ex-
tends SudokuSolver class. This has empty implementation
and added in case you wanted to add some common meth-
ods/attributes for solving standard Sudoku puzzles, but
you don’t have to touch this if you don’t have these. Can
add to.
solver/KillerSudokuSolver.java Abstract class for Killer Sudoku solver algorithms, extends
SudokuSolver class. This has empty implementation and
added in case you wanted to add some common meth-
ods/attributes for solving Killer Sudoku puzzles, but you
don’t have to touch this if you don’t have these. Can add
to.
solver/BackTrackingSolver.java Class for solving standard Sudoku with backtracking.
Please complete the implementation.
solver/AlgorXSolver.java Class for solving standard Sudoku with Algorithm X algo-
rithm. Please complete implementation.
solver/DancingLinksSolver.java Class for solving standard Sudoku with the Dancing Links
approach. Please complete the implementation.
solver/KillerBackTrackingSolver.java Class for solving Killer Sudoku with backtracking. Please
complete the implementation.
solver/KillerAdvancedSolver.java Class for solving Killer Sudoku with your advanced algo-
rithm. Please complete the implementation.
Table 1: Table of supplied Java files.
We also strongly suggest to avoid modifying RmitSudokuTester.java, as they form
the IO code, and any of the interfaces for the abstract classes. If you wish, you may
add java classes/files and methods, but it should be within the structure of the skeleton
code, i.e., keep the same directory structure. Similar to assignment 1, this is to minimise
compiling and running issues. Please ensure there are no compilation errors because of
any modifications. You should implement all the missing functionality in *.java files.
8
Ensure your structure compiles and runs on the core teaching servers. Note that the
onus is on you to ensure correct compilation and behaviour on the core teaching servers
before submission, please heed this warning.
As a friendly reminder, remember how packages work and IDE like Eclipse will auto-
matically add the package qualifiers to files created in their environments. This is a large
source of compile errors on the core teaching servers, so remove these package qualifiers
when testing on the core teaching servers.
Compiling and Executing
To compile the files, run the following command from the root directory (the directory
that RmitSudokuTester.java is in):
javac *.java grid/*.java solver/*.java
Note that for Windows machine, remember to replace ‘/’ with ‘\’.
To run the framework:
java RmitSudokuTester [puzzle fileName] [game type] [solver type]
[visualisation]