Description
1 Programming Assignment
The 9-puzzle consists of a square grid containing eight tiles, marked with the numbers 1 through 8. One
of the spaces in the grid is empty. The initial state of the puzzle is the configuration below:
1 2 3
4 5 6
7 8
This is considered to be the ‘solved’ state of the puzzle and is normally called the ‘goal state’. The tiles on
the board can be moved horizontally or vertically into the empty space to scramble the ordering of the
board, as in the configuration below:
4 1 3
2 6
7 5 8
The programming assignment is to implement a solver for the 9-puzzle. Your submission will read a
sequence of boards and, for each board, output a sequence of moves which solves the board.
The different configurations of the 9-puzzle and their relationships can be modeled with a graph. Each
vertex corresponds to a possible configuration of the board. Edges represent the transformations possible
by making one (legal) move. That is, if two different board configurations are connected by an edge, there
is a way to obtain one configuration from the other by making a single move. To solve a given board, tiles
are moved until the goal state is reached. The diagram below shows a small snapshot of the graph, with
the goal state framed in green.
The set of moves needed to solve a given board is represented by a path in the graph from the board to the
goal state. Therefore, a board can be solved by performing one of the two fundamental graph traversals–
DFS or BFS–on the graph and searching for a path to the goal state. Some possible board configurations
cannot be solved, such as the following:
1 2 3
4 5 6
8 7
Your task is to write class SolveNinePuzzle. The main method in your code should help you test
your implementation by entering test data or reading it from a file.
2 Input Format
9-puzzle boards are input as 3×3 tables, with the character ‘0’ representing the empty square. For
example, the board
4 1 3
2 6
7 5 8
would be represented by the input sequence
4 1 3
0 2 6
7 5 8
3 Suggested Algorithm
If 𝑣 is the vertex corresponding to the input board and 𝑢 is the vertex corresponding to the goal state, then
𝑣 is solvable if and only if a traversal (DFS or BFS) rooted at 𝑣 encounters 𝑢 (or vice-versa in fact). If 𝑢
is never encountered, then SolveNinePuzzle should return false. If 𝑢 is encountered, then the
traversal tree computed by DFS or BFS can be used to find a path from 𝑣 to 𝑢 in the graph (specifically,
by starting at 𝑢 and tracing upward through the tree until 𝑣 is reached). The implementation should print
every board encountered along this path.
The exact implementation of the SolveNinePuzzle program is up to you. However, the algorithm
outlined below is suggested for simplicity:
• Create the vertex 𝑣 of 𝐺 corresponding to the input board 𝐵.
• Create the vertex 𝑢 of 𝐺 corresponding to the goal state.
• Run DFS or BFS on 𝐺 starting at 𝑣.
• If 𝑢 is encountered by the traversal, print each board on the 𝑣 − 𝑢 path and return true.
• Otherwise, return false.
In practice, puzzles like the 9-puzzle and 16-puzzle are solved with more advanced artificial intelligence
algorithms, which are beyond the scope of this course.
An example pseudocode algorithm for solving this problem using DFS is as follows:
Algorithm ninePuzzleDFS(Board 𝐵, Board 𝐺, HashTable 𝐻, Path 𝑃):
Input: Current board 𝐵 as a 3 × 3 integer array, the goal board 𝐺 as a 3 × 3 integer array, hash table
𝐻 and some data structure holding the path so far, 𝑃.
Output: Boolean true is a path exists, and false if one does not exist.
if 𝐵 = 𝐺 then \\ 𝐺 is the goal board
print 𝑃
return true
if 𝐵 is NOT is 𝐻 then \\Vertex 𝐵 is unexplored
add 𝐵 to 𝐻
for each adjacent board, 𝐵𝑖
\\ 𝑖 = 2, 3 or 4 of them
add 𝐵𝑖
to 𝑃
ninePuzzleDFS(𝐵𝑖
,𝐺,𝐻,𝑃)
remove 𝐵𝑖
from 𝑃
return false
end
Each vertex of the underlying graph corresponds to a possible 9-puzzle board, but it can be helpful to
have vertices represented by strings or integers instead of 3×3 arrays to facilitate indexing into a hash
table. To enable this, you may use the Arrays.deepToString(int[][]) to convert the array into
a string. This will allow you to insert the vertices into the java hashing class HashSet. Note, there is no
need to actually create the graph here. We can perform graph algorithms on the vertices even though we
are storing them in a hash table because we know that every vertex has at most 4 adjacent vertices which
can be determined when needed using the given board. So, you can create an abstract version of the graph
on the fly.
4 Test Datasets
A collection of randomly generated solvable and unsolvable boards has been uploaded to conneX. Your
assignment will be tested on boards similar but not identical to the uploaded boards. You may want to
create your own collection of test boards.
5 Sample Run
The output of a model solution on the board specified above is given in the listing below. Note that there
may be multiple move sequences that solve a given board. Console input is shown in blue.
Reading board 1
4 1 3
0 2 6
7 5 8
Attempting to solve board 1…
4 1 3
0 2 6
7 5 8
0 1 3
4 2 6
7 5 8
1 0 3
4 2 6
7 5 8
1 2 3
4 0 6
7 5 8
1 2 3
4 5 6
7 0 8
1 2 3
4 5 6
7 8 0
Board 1: Solvable.
Processed 1 board.
Average Time (seconds): 0.00
6 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated testing and
human inspection. The running time of the implemented algorithm should be at most 𝑂(𝑛
2
), where 𝑛 is
the number of vertices in the constructed graph 𝐺. To receive full marks, the implementation should solve
each board with the smallest number of moves possible. This can be achieved by using BFS instead of
DFS.
Score (/25) Description
0 – 5 Submission does not compile or does not
conform to the provided description.
5 – 15 The implemented algorithm is not 𝑂(𝑛
2
) or is
substantially inaccurate on the tested inputs.
15 – 20 The implemented algorithm is 𝑂(𝑛
2
) and
accurate on all the tested inputs.
20 – 25 The implemented algorithm is 𝑂(𝑛
2
), accurate
on all the tested inputs, and the sequence of
moves for each tested board is the shortest
possible length.
To be properly tested, every submission must compile correctly as submitted. If your submission does
not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of 25. The
best way to make sure your submission is correct is to download it from conneX after submitting and test
it. You are not permitted to revise your submission after the due date, and late submissions will not be
accepted, so you should ensure that you have submitted the correct version of your code before the due
date. conneX will allow you to change your submission before the due date if you notice a mistake. After
submitting your assignment, conneX will automatically send you a confirmation email. If you do not
receive such an email, your submission was not received. If you have problems with the submission
process, send an email to the instructor before the due date.
CSC 225 SUMMER 2016
ALGORITHMS AND DATA STRUCTURES I
ASSIGNMENT 4
UNIVERSITY OF VICTORIA
1. Let 𝐺 be the undirected graph with vertices 𝑉 = {0,1,2,3,4,5,6,7,8} and edges
𝐸 = {{0,4},{1,4},{1,5},{2,3},{2,5},{3,5},{4,5},{4,6},{4,8},{5,6},{5,7},{6,7},{6,8},{7,8}}
(a) Draw 𝐺 in such a way that no two edges cross (i.e. it is a planar graph.)
(b) Draw adjacency list representation of 𝐺.
(c) Draw adjacency matrix representation of 𝐺.
2. For the graph 𝐺 in Problem 1 assume that, in a traversal of 𝐺, the adjacent vertices of a given
vertex are returned in their numeric order.
(a) Order the vertices as they are visited in a DFS traversal starting at vertex 0.
(b) Order the vertices as they are visited in a BFS traversal starting at vertex 0.
3. Let 𝐹 = (𝑉, 𝐸) be a forest with 𝑛 vertices, 𝑚 edges and 𝑘 connected components. Prove that the
number of edges in 𝐹 is 𝑚 = 𝑛 − 𝑘.
4. Design an algorithm (in pseudocode) to determine whether a digraph has a unique topological
ordering. Your algorithm should return the ordering if a unique one exists or indicate that no
unique order exists.
5. A 2-colouring of an undirected graph with n vertices and m edges is the assignment of one of two
colours (say, black or white) to each vertex of the graph, so that no two adjacent nodes have the
same colour. So, if there is an edge (u,v) in the graph, either node u is black and v is white or vice
versa. Give an O(n + m) time algorithm (pseudocode!) to 2-colour a graph or determine that no
such colouring exists, and justify the running time. The following shows examples of graphs that
are and are not 2-colourable:
2-colourable Not 2-colourable
