UNIVERSITY OF SOUTH AFRICA
College of Science, Engineering and Technology
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751: Artificial Intelligence
Assignment 02 — Semester 1, 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751
Module Code:
Artificial Intelligence
Module Name:
Assignment 02
Assignment Title:
265002
Assignment Number:
22 July 2026
Due Date:
80
Total Marks:
Submitted in partial fulfilment of the requirements for COS3751 — UNISA 2026
,UNISA | COS3751 Assignment 02 — Artificial Intelligence
Question 1: Constraint Satisfaction Problems
Constraint Satisfaction Problems (CSPs) form a central framework in artificial intelligence
for modelling and solving combinatorial problems by expressing them as sets of variables,
domains, and constraints (Russell and Norvig, 2021:202).
1.1 The Three Components of a CSP Using Standard Notation
A Constraint Satisfaction Problem is formally defined by the triple ⟨X, D, C⟩, where each
component serves a distinct role (Russell and Norvig, 2021:202):
• X is a set of variables: X = {X1 , X2 , . . . , Xn }. Each variable represents an unknown that
must be assigned a value. For example, in a map-colouring problem the variables might be
the regions of a country.
• D is a set of domains: D = {D1 , D2 , . . . , Dn }. Each domain Di contains the finite set of
values that variable Xi may take. In the map-colouring example, every Di = {Red, Green, Blue}.
• C is a set of constraints: C = {C1 , C2 , . . . , Cm }. Each constraint Cj specifies which com-
binations of values are allowed for some subset of variables. In map colouring, each con-
straint states that two adjacent regions must receive different colours.
A solution is a complete assignment of values to all variables such that every constraint in C
is satisfied.
1.2 Binary Constraints vs Higher-Order Constraints
Key Distinction
Binary constraint: A constraint that involves exactly two variables. It restricts the
combination of values that the two variables may simultaneously hold.
Higher-order constraint: A constraint that involves three or more variables, restrict-
ing the joint assignment across that larger set.
Real example of a binary constraint: In the South African Matric timetable problem, no
two subjects that share a large cohort of candidates may be scheduled in the same time slot.
If XMaths and XPhysics represent their respective exam slots, the constraint XMaths ̸= XPhysics
is binary because it involves exactly two variables.
Page 2 of 18
, UNISA | COS3751 Assignment 02 — Artificial Intelligence
Real example of a higher-order constraint: In a Sudoku puzzle, the AllDifferent con-
straint applied to an entire row of nine cells involves nine variables simultaneously: AllDifferent(X1 , X2 , . . . , X9 )
This is a global (higher-order) constraint because it restricts the joint assignment of more than
two variables at once (Russell and Norvig, 2021:205).
1.3 Backtracking Search for CSPs
(a) Why Backtracking Search is a Depth-First Search Algorithm
Backtracking search for CSPs operates as a depth-first search because it assigns values to
variables one at a time, going deeper in the search tree with each assignment. When an in-
consistency is detected, the algorithm backtracks to the most recently assigned variable and
tries a different value, rather than restarting from the root. The search therefore explores one
complete branch of the assignment tree before considering alternatives, which is the defining
characteristic of depth-first search (Russell and Norvig, 2021:214–215). The search tree has
depth n (the number of variables), and at each node one variable is assigned a value from its
domain.
(b) Commutativity of Variable Assignments
Variable assignments in a CSP are commutative because the order in which variables are
assigned does not affect the final set of solutions; the same complete assignments are reachable
regardless of the sequence in which variables are chosen. For example, assigning X1 = Red
then X2 = Blue leads to the same state as assigning X2 = Blue first and X1 = Red second.
This property is important for efficiency because it allows backtracking search to fix a single
variable ordering and explore only one permutation of assignments rather than all n! order-
ings. Without commutativity, the algorithm would need to consider every possible ordering of
assignments, multiplying the search space enormously (Russell and Norvig, 2021:214).
1.4 Heuristics for Improving Backtracking Search
MRV targets the variable most likely to cause failure soon, called the “fail-first” strategy.
By assigning it early, failures are detected near the top of the search tree where pruning has
the greatest impact (Russell and Norvig, 2021:216). The Degree heuristic acts as a tie-
breaker when multiple variables have the same domain size; it selects the variable that is most
Page 3 of 18
College of Science, Engineering and Technology
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751: Artificial Intelligence
Assignment 02 — Semester 1, 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
COS3751
Module Code:
Artificial Intelligence
Module Name:
Assignment 02
Assignment Title:
265002
Assignment Number:
22 July 2026
Due Date:
80
Total Marks:
Submitted in partial fulfilment of the requirements for COS3751 — UNISA 2026
,UNISA | COS3751 Assignment 02 — Artificial Intelligence
Question 1: Constraint Satisfaction Problems
Constraint Satisfaction Problems (CSPs) form a central framework in artificial intelligence
for modelling and solving combinatorial problems by expressing them as sets of variables,
domains, and constraints (Russell and Norvig, 2021:202).
1.1 The Three Components of a CSP Using Standard Notation
A Constraint Satisfaction Problem is formally defined by the triple ⟨X, D, C⟩, where each
component serves a distinct role (Russell and Norvig, 2021:202):
• X is a set of variables: X = {X1 , X2 , . . . , Xn }. Each variable represents an unknown that
must be assigned a value. For example, in a map-colouring problem the variables might be
the regions of a country.
• D is a set of domains: D = {D1 , D2 , . . . , Dn }. Each domain Di contains the finite set of
values that variable Xi may take. In the map-colouring example, every Di = {Red, Green, Blue}.
• C is a set of constraints: C = {C1 , C2 , . . . , Cm }. Each constraint Cj specifies which com-
binations of values are allowed for some subset of variables. In map colouring, each con-
straint states that two adjacent regions must receive different colours.
A solution is a complete assignment of values to all variables such that every constraint in C
is satisfied.
1.2 Binary Constraints vs Higher-Order Constraints
Key Distinction
Binary constraint: A constraint that involves exactly two variables. It restricts the
combination of values that the two variables may simultaneously hold.
Higher-order constraint: A constraint that involves three or more variables, restrict-
ing the joint assignment across that larger set.
Real example of a binary constraint: In the South African Matric timetable problem, no
two subjects that share a large cohort of candidates may be scheduled in the same time slot.
If XMaths and XPhysics represent their respective exam slots, the constraint XMaths ̸= XPhysics
is binary because it involves exactly two variables.
Page 2 of 18
, UNISA | COS3751 Assignment 02 — Artificial Intelligence
Real example of a higher-order constraint: In a Sudoku puzzle, the AllDifferent con-
straint applied to an entire row of nine cells involves nine variables simultaneously: AllDifferent(X1 , X2 , . . . , X9 )
This is a global (higher-order) constraint because it restricts the joint assignment of more than
two variables at once (Russell and Norvig, 2021:205).
1.3 Backtracking Search for CSPs
(a) Why Backtracking Search is a Depth-First Search Algorithm
Backtracking search for CSPs operates as a depth-first search because it assigns values to
variables one at a time, going deeper in the search tree with each assignment. When an in-
consistency is detected, the algorithm backtracks to the most recently assigned variable and
tries a different value, rather than restarting from the root. The search therefore explores one
complete branch of the assignment tree before considering alternatives, which is the defining
characteristic of depth-first search (Russell and Norvig, 2021:214–215). The search tree has
depth n (the number of variables), and at each node one variable is assigned a value from its
domain.
(b) Commutativity of Variable Assignments
Variable assignments in a CSP are commutative because the order in which variables are
assigned does not affect the final set of solutions; the same complete assignments are reachable
regardless of the sequence in which variables are chosen. For example, assigning X1 = Red
then X2 = Blue leads to the same state as assigning X2 = Blue first and X1 = Red second.
This property is important for efficiency because it allows backtracking search to fix a single
variable ordering and explore only one permutation of assignments rather than all n! order-
ings. Without commutativity, the algorithm would need to consider every possible ordering of
assignments, multiplying the search space enormously (Russell and Norvig, 2021:214).
1.4 Heuristics for Improving Backtracking Search
MRV targets the variable most likely to cause failure soon, called the “fail-first” strategy.
By assigning it early, failures are detected near the top of the search tree where pruning has
the greatest impact (Russell and Norvig, 2021:216). The Degree heuristic acts as a tie-
breaker when multiple variables have the same domain size; it selects the variable that is most
Page 3 of 18
