UNIVERSITY OF SOUTH AFRICA
College of Science, Engineering and Technology – School of Computing
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751: Techniques of Artificial Intelligence
Assignment 03 | 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751
Module Code:
Techniques of Artificial Intelligence
Module Name:
Problem Solving, AI, Ethics and the Future
Assignment Topic:
of AI
Assignment 03
Assignment Number:
268281
Unique Number:
11 September 2026
Due Date:
100
Total Marks:
Submitted in partial fulfilment of the requirements
for Techniques of Artificial Intelligence, UNISA 2026
,UNISA | COS3751 Techniques of Artificial Intelligence – Assignment 03
Question 1: Solving Problems by Searching
The 8-puzzle and the numbered state-space in this question both illustrate how a problem
must be reduced to states, operators and a goal test before any search strategy can be ap-
plied to it (Russell and Norvig, 2021).
1.1 The 8-Puzzle
The 8-puzzle is a classic puzzle consisting of a 3 × 3 board with 8 numbered tiles and one
blank space. Any tile adjacent to the blank space can slide into the empty space. In the start
state shown in Figure 1, tiles 5, 6, and 7 are adjacent to the blank space and can therefore be
moved. The goal is to move one tile at a time into the blank space until the goal configuration
shown in Figure 2 is reached.
a) Represent the initial state and goal state formally.
A state of the 8-puzzle can be represented as an ordered 9-tuple read row by row, left to right,
with 0 denoting the blank space. This representation is adequate because it captures the
exact position of every tile, allowing a search algorithm to generate successor states simply
by swapping the position of 0 with an adjacent tile (Russell and Norvig, 2021).
From Figure 1, the initial state is:
S0 = (2, 8, 3, 1, 6, 4, 7, 0, 5)
From Figure 2, the goal state is:
G = (1, 2, 3, 4, 5, 6, 7, 8, 0)
b) List the legal moves possible from the initial state.
The blank occupies the bottom-middle cell of the grid. A legal move slides any tile that is
orthogonally adjacent to the blank into that position. From the initial state, three tiles satisfy
this condition:
1. Tile 6 (directly above the blank) can move down.
Page 2 of 23
, UNISA | COS3751 Techniques of Artificial Intelligence – Assignment 03
2. Tile 7 (directly left of the blank) can move right.
3. Tile 5 (directly right of the blank) can move left.
Legal moves from S0 : {6, 7, 5}
c) Using a suitable search strategy, show the sequence of moves required to reach the goal state.
Before any search strategy is applied, the state space should be checked for reachability,
since not every arrangement of the 8-puzzle is solvable from every other arrangement (Rus-
sell and Norvig, 2021). Solvability is determined by the parity of the number of inversions in
the tile sequence, where an inversion is any pair of tiles that appears in the wrong relative
order compared with the goal, ignoring the blank.
Reading the initial state row by row and omitting the blank gives the sequence:
2, 8, 3, 1, 6, 4, 7, 5
Counting every pair that is out of order against the natural ascending order produces:
Inversions = 1 + 6 + 1 + 0 + 2 + 0 + 1 = 11
The goal state, read the same way, is 1, 2, 3, 4, 5, 6, 7, 8, which contains zero inversions. For a
3 × 3 sliding puzzle, a state can only be transformed into another by legal moves if both states
have the same inversion parity, because every horizontal slide leaves the parity unchanged
and every vertical slide changes it by an even number of transpositions. Eleven is odd and
zero is even, so the two states belong to different equivalence classes of the state space and
no sequence of legal moves connects them.
No sequence of legal moves exists from S0 to G.
If a search strategy such as breadth-first search were applied regardless, it would exhaus-
tively expand every state reachable from S0 and terminate having found no state matching G,
since G lies outside the reachable state space. This is not an error in the search procedure;
it is a property of the puzzle instance itself, and correctly identifying it is part of applying the
Page 3 of 23
College of Science, Engineering and Technology – School of Computing
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751: Techniques of Artificial Intelligence
Assignment 03 | 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751
Module Code:
Techniques of Artificial Intelligence
Module Name:
Problem Solving, AI, Ethics and the Future
Assignment Topic:
of AI
Assignment 03
Assignment Number:
268281
Unique Number:
11 September 2026
Due Date:
100
Total Marks:
Submitted in partial fulfilment of the requirements
for Techniques of Artificial Intelligence, UNISA 2026
,UNISA | COS3751 Techniques of Artificial Intelligence – Assignment 03
Question 1: Solving Problems by Searching
The 8-puzzle and the numbered state-space in this question both illustrate how a problem
must be reduced to states, operators and a goal test before any search strategy can be ap-
plied to it (Russell and Norvig, 2021).
1.1 The 8-Puzzle
The 8-puzzle is a classic puzzle consisting of a 3 × 3 board with 8 numbered tiles and one
blank space. Any tile adjacent to the blank space can slide into the empty space. In the start
state shown in Figure 1, tiles 5, 6, and 7 are adjacent to the blank space and can therefore be
moved. The goal is to move one tile at a time into the blank space until the goal configuration
shown in Figure 2 is reached.
a) Represent the initial state and goal state formally.
A state of the 8-puzzle can be represented as an ordered 9-tuple read row by row, left to right,
with 0 denoting the blank space. This representation is adequate because it captures the
exact position of every tile, allowing a search algorithm to generate successor states simply
by swapping the position of 0 with an adjacent tile (Russell and Norvig, 2021).
From Figure 1, the initial state is:
S0 = (2, 8, 3, 1, 6, 4, 7, 0, 5)
From Figure 2, the goal state is:
G = (1, 2, 3, 4, 5, 6, 7, 8, 0)
b) List the legal moves possible from the initial state.
The blank occupies the bottom-middle cell of the grid. A legal move slides any tile that is
orthogonally adjacent to the blank into that position. From the initial state, three tiles satisfy
this condition:
1. Tile 6 (directly above the blank) can move down.
Page 2 of 23
, UNISA | COS3751 Techniques of Artificial Intelligence – Assignment 03
2. Tile 7 (directly left of the blank) can move right.
3. Tile 5 (directly right of the blank) can move left.
Legal moves from S0 : {6, 7, 5}
c) Using a suitable search strategy, show the sequence of moves required to reach the goal state.
Before any search strategy is applied, the state space should be checked for reachability,
since not every arrangement of the 8-puzzle is solvable from every other arrangement (Rus-
sell and Norvig, 2021). Solvability is determined by the parity of the number of inversions in
the tile sequence, where an inversion is any pair of tiles that appears in the wrong relative
order compared with the goal, ignoring the blank.
Reading the initial state row by row and omitting the blank gives the sequence:
2, 8, 3, 1, 6, 4, 7, 5
Counting every pair that is out of order against the natural ascending order produces:
Inversions = 1 + 6 + 1 + 0 + 2 + 0 + 1 = 11
The goal state, read the same way, is 1, 2, 3, 4, 5, 6, 7, 8, which contains zero inversions. For a
3 × 3 sliding puzzle, a state can only be transformed into another by legal moves if both states
have the same inversion parity, because every horizontal slide leaves the parity unchanged
and every vertical slide changes it by an even number of transpositions. Eleven is odd and
zero is even, so the two states belong to different equivalence classes of the state space and
no sequence of legal moves connects them.
No sequence of legal moves exists from S0 to G.
If a search strategy such as breadth-first search were applied regardless, it would exhaus-
tively expand every state reachable from S0 and terminate having found no state matching G,
since G lies outside the reachable state space. This is not an error in the search procedure;
it is a property of the puzzle instance itself, and correctly identifying it is part of applying the
Page 3 of 23
