School of Computer Science
COMPSCI 367 Assignment 2 due 8 October 2023
Due: by 11:59pm on the due date. Late assignments will not be marked.
Total mark: 15.
Worth: This assignment counts towards 15% of your final mark.
Please answer ALL questions. Submit the answer to Question 1 as a pdf file Q1.pdf. Submit
the answers to Question 2 and Question 3 as Prolog code, i.e., .pl files, as mapcolouring.pl
and surround.pl, respectively.
1. [5 marks] Suppose you are building a decision support system that helps people with investment options. The system assumes that the user has some money to invest and can help select
among the following possibilities:
• an income fund
• a growth fund
• a conservative fund
You will build a simple knowledge base, consisting of a set of rules written below (in a slightly
abbreviated form). Each rule is written as an implication, expressed in terms of an if part (the
premise) and a then part (the conclusion). The conclusion conservative, income, growth
are the three fund possibilities.
For example, rule (3) delivers the following message: “If you are retired and you have basic
insurance coverage, then the category of fund to select is the income fund”.
(1) if have health insurance and have life insurance
then basic insurance coverage
(2) if investment for retirement and basic insurance coverage
then conservative
(3) if retired and basic insurance coverage
then income
(4) if investment for children education and basic insurance coverage
then growth
(5) if investment for home ownership and basic insurance coverage
then growth
(6) if age≤65
then not retired
COMPSCI 367 Assignment 2 Page 1 of 4
(7) if age>65
then retired
(8) if not retired and no pension
then investment for retirement
(9) if have children and children’s education not funded
then investment for children education
(10) if no home ownership and want home
then investment for home ownership
Answer the following questions and write down the solutions in Q1.pdf file. Clearly indicate
the solutions to (a) and (b):
(a) [2 marks] Design a definite clause knowledge base using the information above. Clearly
list the atomic propositions (with their intended meaning) and the clauses in the KB. An
example that contains a few atomic propositions and a rule is given below:
Example. Atomic propositions:
• BasInsure: The user has basic insurance cover
• HeaInsure: The user has health insurance
• LifInsure: The user has life insurance
Clause (1): BasInsure ← HeaInsure ∧ LifInsure
(b) [3 marks] Suppose a user has the following information:
(11) is 42 years old
(12) has health insurance, and (13) life insurance
(14) not covered by a pension plan
(15) has one child, age 12, who (16) does not have funding for education
(17) does not currently own a house and (18) would like to own one.
Apply SLD resolution on the three queries
i. ask conservative
ii. ask income
iii. ask growth
For each case, provide a proof if the answer is true, and answer why if the answer is false.
2. [4 marks] Solve the map colouring problem for North Island using Prolog. Up to three colours,
red, green, blue, are allowed to use. Two adjacent regions cannot be marked with the same
colour.
You may use the following knowledge base:
• different(red, green).
• different(red, blue).
• different(green, blue).
COMPSCI 367 Assignment 2 Page 2 of 4
• different(green, red).
• different(blue, red).
• different(blue, green).
Implement a Prolog predicate mapcolouring(N,A,WA,B,G,T,M,H,WE) where a variable should
be the corresponding word as indicated in the following map. Submit your answer as
mapcolouring.pl file.
3. [6 marks] Given is a 4 × 4 board with each grid marked with either “+” or “−”. The goal
is to find all − grids that are surrounded by +. A − grid at the edge cannot be surrounded.
More formally, each grid can have up to 4 neighbour grids, i.e., top, bottom, left and right. If
one grid or a group of “−” grids forms a “connected” area and their neighbours are all “+”
grids, then all “−” grids in this group are surrounded. Otherwise, if any a − grid in that group
has a − neighbour that is at the edge, then all neg grids in this group are non-surrounded. For
example, in figure (a), the − grids highlighted in red are surrounded; in figure (b), no − grid
is surrounded.
Use the constants g11, g12, . . . , g44 to denote the coordinates of grids. Use the rules neg(G)
and pos(G) to denote a grid marked with − and +, respectively, where the variable G ∈ {g11,
g12, . . . , g44}.
You are requested to: Build a knowledge base and implement a Prolog predicate
is surrounded (G) such that is surrounded (G) is true if G is a − grid and is surrounded by + grids, and false otherwise. You are allowed to define any additional and auxiliary
rules.
COMPSCI 367 Assignment 2 Page 3 of 4
Evaluation. Your programme may be tested using different configurations of the board. For
example, the configuration code for the figure (a) is:
neg(g21).
neg(g23).
neg(g32).
neg(g33).
pos(g11).
pos(g12).
pos(g13).
pos(g14).
pos(g22).
pos(g24).
pos(g31).
pos(g34).
pos(g41).
pos(g42).
pos(g43).
pos(g44).
The configuration code will be added at the top of the knowledge base when testing.
Submit your answer as surround.pl file.