UNIVERSITY OF SOUTH AFRICA (UNISA)
College of Science, Engineering and Technology
⋄
Problem Solving, AI, Ethics
and the Future of AI
Assignment 03 — 2026
⋄
Module Code: COS3751
Module Name: Artificial Intelligence
Assignment No.: Assignment 03
Due Date: 11 September 2026
Semester: Semester 2, 2026
Unique Number: 268281
Submitted in partial fulfilment of the requirements for Artificial Intelligence
at the University of South Africa.
,UNISA | COS3751 Problem Solving, AI, Ethics and the Future of AI
Question 1: Solving Problems by Searching
The 8-puzzle in Figures 1 and 2 of the assignment provides a compact but non-trivial state-
space search problem, and the second part of this question extends the same search con-
cepts to an abstract state space generated by the successor rule k → {2k, 2k + 1}.
1.1(a) Formal representation of the initial and goal states
Represent the initial state and goal state formally.
Reading the board row by row, left to right, top to bottom, and using 0 to denote the blank, the
initial state in Figure 1 and the goal state in Figure 2 are represented as ordered 9-tuples:
S0 = (2, 8, 3, 1, 6, 4, 7, 0, 5)
G = (1, 2, 3, 4, 5, 6, 7, 8, 0)
This tuple notation is the standard way of encoding an 8-puzzle configuration for search (Rus-
sell and Norvig, 2021:64). Each distinct arrangement of the tiles corresponds to exactly one
state in the search space, and a successor function can generate new states by swapping the
blank with whichever tile is vertically or horizontally adjacent to it.
1.1(b) Legal moves from the initial state
List the legal moves possible from the initial state.
In the initial configuration the blank occupies the bottom-middle cell:
2 8 3
1 6 4
7 □ 5
Three tiles are orthogonally adjacent to the blank and can therefore slide into it: tile 6 (directly
above the blank) can move down, tile 7 (to the left of the blank) can move right, and tile 5 (to
the right of the blank) can move left. The legal moves from S0 are:
{move 6 down, move 7 right, move 5 left}
Page 1 of 23
, UNISA | COS3751 Problem Solving, AI, Ethics and the Future of AI
1.1(c) Sequence of moves to reach the goal state
Using a suitable search strategy, show the sequence of moves required to reach the goal state.
Before applying a search strategy such as breadth-first search, it is worth checking whether
the supplied goal is even reachable from the supplied start, because the 8-puzzle is only
solvable from roughly half of all possible starting arrangements (Russell and Norvig, 2021:66).
Solvability is governed by the parity of the number of inversions in the tile sequence, where an
inversion is any pair of tiles that appears out of the order they hold in the goal state.
Listing the initial state’s tiles in reading order, ignoring the blank, gives the sequence 2, 8, 3, 1, 6, 4, 7, 5.
Counting inversions against the goal ordering 1, 2, 3, 4, 5, 6, 7, 8:
• 2 precedes 1: 1 inversion
• 8 precedes 3,1,6,4,7,5: 6 inversions
• 3 precedes 1: 1 inversion
• 6 precedes 4,5: 2 inversions
• 4 precedes none smaller after it: 0
• 7 precedes 5: 1 inversion
This gives a total of 1 + 6 + 1 + 2 + 0 + 1 = 11 inversions, which is odd. The goal state has
0 inversions, which is even. On a 3 × 3 board, a legal slide of a tile into the blank changes the
inversion count by an even number, so the parity of the inversion count is invariant under legal
moves (Russell and Norvig, 2021:66). Since S0 has odd parity and G has even parity, no finite
sequence of legal moves can transform S0 into G.
The supplied 8-puzzle is therefore unsolvable: the initial arrangement contains 11 inversions
while the goal contains 0, and because a legal move never changes inversion parity, no legal
sequence of moves connects the two states. A breadth-first search launched from S0 would
exhaustively expand the entire reachable half of the state space without ever generating G,
which illustrates why checking solvability analytically is more efficient than relying on search
alone to discover that a goal is unreachable.
1.1(d) Why the 8-puzzle is used in AI search problems
Briefly explain why the 8-puzzle is commonly used in artificial intelligence (AI) search problems.
The 8-puzzle is a standard teaching example because its rules are trivial to state while its
Page 2 of 23
College of Science, Engineering and Technology
⋄
Problem Solving, AI, Ethics
and the Future of AI
Assignment 03 — 2026
⋄
Module Code: COS3751
Module Name: Artificial Intelligence
Assignment No.: Assignment 03
Due Date: 11 September 2026
Semester: Semester 2, 2026
Unique Number: 268281
Submitted in partial fulfilment of the requirements for Artificial Intelligence
at the University of South Africa.
,UNISA | COS3751 Problem Solving, AI, Ethics and the Future of AI
Question 1: Solving Problems by Searching
The 8-puzzle in Figures 1 and 2 of the assignment provides a compact but non-trivial state-
space search problem, and the second part of this question extends the same search con-
cepts to an abstract state space generated by the successor rule k → {2k, 2k + 1}.
1.1(a) Formal representation of the initial and goal states
Represent the initial state and goal state formally.
Reading the board row by row, left to right, top to bottom, and using 0 to denote the blank, the
initial state in Figure 1 and the goal state in Figure 2 are represented as ordered 9-tuples:
S0 = (2, 8, 3, 1, 6, 4, 7, 0, 5)
G = (1, 2, 3, 4, 5, 6, 7, 8, 0)
This tuple notation is the standard way of encoding an 8-puzzle configuration for search (Rus-
sell and Norvig, 2021:64). Each distinct arrangement of the tiles corresponds to exactly one
state in the search space, and a successor function can generate new states by swapping the
blank with whichever tile is vertically or horizontally adjacent to it.
1.1(b) Legal moves from the initial state
List the legal moves possible from the initial state.
In the initial configuration the blank occupies the bottom-middle cell:
2 8 3
1 6 4
7 □ 5
Three tiles are orthogonally adjacent to the blank and can therefore slide into it: tile 6 (directly
above the blank) can move down, tile 7 (to the left of the blank) can move right, and tile 5 (to
the right of the blank) can move left. The legal moves from S0 are:
{move 6 down, move 7 right, move 5 left}
Page 1 of 23
, UNISA | COS3751 Problem Solving, AI, Ethics and the Future of AI
1.1(c) Sequence of moves to reach the goal state
Using a suitable search strategy, show the sequence of moves required to reach the goal state.
Before applying a search strategy such as breadth-first search, it is worth checking whether
the supplied goal is even reachable from the supplied start, because the 8-puzzle is only
solvable from roughly half of all possible starting arrangements (Russell and Norvig, 2021:66).
Solvability is governed by the parity of the number of inversions in the tile sequence, where an
inversion is any pair of tiles that appears out of the order they hold in the goal state.
Listing the initial state’s tiles in reading order, ignoring the blank, gives the sequence 2, 8, 3, 1, 6, 4, 7, 5.
Counting inversions against the goal ordering 1, 2, 3, 4, 5, 6, 7, 8:
• 2 precedes 1: 1 inversion
• 8 precedes 3,1,6,4,7,5: 6 inversions
• 3 precedes 1: 1 inversion
• 6 precedes 4,5: 2 inversions
• 4 precedes none smaller after it: 0
• 7 precedes 5: 1 inversion
This gives a total of 1 + 6 + 1 + 2 + 0 + 1 = 11 inversions, which is odd. The goal state has
0 inversions, which is even. On a 3 × 3 board, a legal slide of a tile into the blank changes the
inversion count by an even number, so the parity of the inversion count is invariant under legal
moves (Russell and Norvig, 2021:66). Since S0 has odd parity and G has even parity, no finite
sequence of legal moves can transform S0 into G.
The supplied 8-puzzle is therefore unsolvable: the initial arrangement contains 11 inversions
while the goal contains 0, and because a legal move never changes inversion parity, no legal
sequence of moves connects the two states. A breadth-first search launched from S0 would
exhaustively expand the entire reachable half of the state space without ever generating G,
which illustrates why checking solvability analytically is more efficient than relying on search
alone to discover that a goal is unreachable.
1.1(d) Why the 8-puzzle is used in AI search problems
Briefly explain why the 8-puzzle is commonly used in artificial intelligence (AI) search problems.
The 8-puzzle is a standard teaching example because its rules are trivial to state while its
Page 2 of 23
