# Java代写 | COSC 1285 / COSC 2123   Assignment 2: Solving Sudoku

Algorithms and Analysis COSC 1285 / COSC 2123
Assignment 2: Solving Sudoku
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.
3
Introduction and Background
Sudoku was a game ﬁrst 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 ﬁlled 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 ﬁlled in
with discrete values from 1-9. Sudoku puzzles have some of these cells pre-ﬁlled with
values, and the aim is to ﬁll 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
2
3
4
. Every cell is assigned a value between 1 to 9.
. Every row contains 9 unique values from 1 to 9.
. Every column contains 9 unique values from 1 to 9.
. 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-ﬁlled in. After ﬁlling 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.
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 ﬁrst 4 are the same as standard Sudoku):
1
2
3
4
5
. Every cell is assigned a value between 1 to 9.
. Every row contains 9 unique values from 1 to 9.
. Every column contains 9 unique values from 1 to 9.
. Every 3 by 3 block/box contains 9 unique values from 1 to 9.
. The sum of values in the cells of each cage must be equal to the cage target total
and all the values in a cage must be unique.
2
As an example, consider Figure 2. Figure 2a shows the initial puzzle. Note the cages
are in diﬀerent 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 ﬁnd 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 ﬁrst 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: {i , i }, {i , i , i }, {i , i , i }, {i , i } and {i }, a possible set cover is to select
1
3
2
3
4
1
5
6
2
5
6
{
i , i , i } and {i , i , i }, whose union includes all 6 possible items and they contain no
2 3 4 1 5 6
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
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
1
{
{
i , i , i }
2
3
4
i , i , i }
1
5
6
{
i , i }
2
5
{
i }
6
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}
i , i , i }
0
1
1
0
1
0
1
0
0
1
0
1
1
5
6 E-mail: [email protected]  微信:itcsdx 