Starting from:
$29
Nine Puzzle Assignment
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:
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:
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 information about the puzzle given here is meant to be a basic summary; for more detailed
information, see the additional notes in the resources tab of conneX1.
1The Wikipedia page http://en.wikipedia.org/wiki/15_puzzle also contains some helpful information about
puzzles of this type.
1The different configurations of the 9-puzzle and their relationships can be modelled 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:
A Java template has been provided containing an empty method SolveNinePuzzle, which takes a
3 × 3 integer array B as its only argument. The expected behaviour of the method is as follows:
2Input: A 3 × 3 array B representing a 9-puzzle board.
Output: true if B is solvable and false otherwise.
Side Effects: If the board is solvable, a sequence of boards will be printed representing each step of the solution (starting with the initial board
and ending with the solved board.
Your task is to write the body of the SolveNinePuzzle method. You must use the provided Java
template as the basis of your submission, and put your implementation inside the SolveNinePuzzle
method in the template. You may not change the name, return type or parameters of the
SolveNinePuzzle method. You may add additional methods as needed. The main method in the
template contains code to help you test your implementation by entering test data or reading it
from a file. You may modify the main method, but only the contents of the SolveNinePuzzle
method (and any methods you have added) will be marked. Please read through the comments in
the template file before starting.
2 Input Format
9-puzzle boards are input as 3 × 3 tables, with the character ‘0’ representing the empty square. For
example, the board
would be represented by the input sequence
4 1 3
0 2 6
7 5 8
3 Suggested Algorithm
The exact implementation of the SolveNinePuzzle method is up to you. However, the algorithm
outlined below is suggested for simplicity:
• Construct the graph G of all states of the 9-puzzle.
• Find the vertex v of G corresponding to the input board B.
• Find the vertex u of G corresponding to the goal state.
• Run DFS or BFS on G starting at u.
• If v was encountered by the traversal, print each board on the v-u path and return true.
• Otherwise, return false.
3In 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.
Pseudocode for constructing G can be found in the additional notes in the resources tab of
conneX. Each vertex of G corresponds to a possible 9-puzzle board, but it can be helpful to have
vertices represented by integers instead of 3 × 3 arrays to facilitate indexing into an adjacency list
structure. To enable this, you have been provided with two functions in the template:
• getBoardFromIndex(i): Given a board index i, return the corresponding board.
• getIndexFromBoard(B): Given a board B, return the corresponding index.
These functions will allow you to construct G as if vertices were integers. Since the number of
vertices in G is large, you are encouraged to use an adjacency list representation for the graph.
If v is the vertex corresponding to the input board and u is the vertex corresponding to the goal
state, then v is solvable if and only if a traversal (DFS or BFS) rooted at u encounters v. If v is never
encountered, then SolveNinePuzzle should return false. If v is encountered, then the traversal
tree computed by DFS or BFS can be used to find a path from u to v in the graph (specifically, by
starting at v and tracing upward through the tree until u is reached). The implementation should
print every board encountered along this path using the provided method printBoard(B). If your
submission prints boards using any other means, it may lose marks.
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.
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:
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:
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 information about the puzzle given here is meant to be a basic summary; for more detailed
information, see the additional notes in the resources tab of conneX1.
1The Wikipedia page http://en.wikipedia.org/wiki/15_puzzle also contains some helpful information about
puzzles of this type.
1The different configurations of the 9-puzzle and their relationships can be modelled 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:
A Java template has been provided containing an empty method SolveNinePuzzle, which takes a
3 × 3 integer array B as its only argument. The expected behaviour of the method is as follows:
2Input: A 3 × 3 array B representing a 9-puzzle board.
Output: true if B is solvable and false otherwise.
Side Effects: If the board is solvable, a sequence of boards will be printed representing each step of the solution (starting with the initial board
and ending with the solved board.
Your task is to write the body of the SolveNinePuzzle method. You must use the provided Java
template as the basis of your submission, and put your implementation inside the SolveNinePuzzle
method in the template. You may not change the name, return type or parameters of the
SolveNinePuzzle method. You may add additional methods as needed. The main method in the
template contains code to help you test your implementation by entering test data or reading it
from a file. You may modify the main method, but only the contents of the SolveNinePuzzle
method (and any methods you have added) will be marked. Please read through the comments in
the template file before starting.
2 Input Format
9-puzzle boards are input as 3 × 3 tables, with the character ‘0’ representing the empty square. For
example, the board
would be represented by the input sequence
4 1 3
0 2 6
7 5 8
3 Suggested Algorithm
The exact implementation of the SolveNinePuzzle method is up to you. However, the algorithm
outlined below is suggested for simplicity:
• Construct the graph G of all states of the 9-puzzle.
• Find the vertex v of G corresponding to the input board B.
• Find the vertex u of G corresponding to the goal state.
• Run DFS or BFS on G starting at u.
• If v was encountered by the traversal, print each board on the v-u path and return true.
• Otherwise, return false.
3In 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.
Pseudocode for constructing G can be found in the additional notes in the resources tab of
conneX. Each vertex of G corresponds to a possible 9-puzzle board, but it can be helpful to have
vertices represented by integers instead of 3 × 3 arrays to facilitate indexing into an adjacency list
structure. To enable this, you have been provided with two functions in the template:
• getBoardFromIndex(i): Given a board index i, return the corresponding board.
• getIndexFromBoard(B): Given a board B, return the corresponding index.
These functions will allow you to construct G as if vertices were integers. Since the number of
vertices in G is large, you are encouraged to use an adjacency list representation for the graph.
If v is the vertex corresponding to the input board and u is the vertex corresponding to the goal
state, then v is solvable if and only if a traversal (DFS or BFS) rooted at u encounters v. If v is never
encountered, then SolveNinePuzzle should return false. If v is encountered, then the traversal
tree computed by DFS or BFS can be used to find a path from u to v in the graph (specifically, by
starting at v and tracing upward through the tree until u is reached). The implementation should
print every board encountered along this path using the provided method printBoard(B). If your
submission prints boards using any other means, it may lose marks.
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.
1 file (317.2KB)
