Introduction to Artificial Intelligence
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP3308 – Introduction to Artificial Intelligence
Page 1 of 5
Assignment 1: Search Methods
Deadline
This assignment is worth 12 marks = 12% of your final mark. It is an individual assignment.
Late submissions policy
Late submissions are allowed for up to 3 days late. A penalty of 5% per day late will apply. Assignments more
than 3 days late will not be accepted (i.e. will get 0 marks). The day cut-off time is 11:59pm.
Programming languages
Your implementation can be written in Python, Java, C, C++ or MATLAB. The assignment will be tested using
the language versions as described in the “How your program will be run” section below, so it is important
that your program can be run in the specified versions.
Submission
Your assignment must be submitted using PASTA
If you are off-campus, you’ll need to be connected to the university VPN in order to access the PASTA website.
You can read this page to find out how to connect to the VPN. The students in China should use the new VPN,
which is the special VPN for accessing university resources from China. If you are on-campus and connected
to the University wireless network, you don’t need a VPN to access PASTA.
PASTA will allow you to make as many submissions as you wish, and each submission will provide you with
feedback on each of the components of the assignment. You last submission before the assignment deadline
will be marked, and the mark displayed on PASTA will be the final mark for your assignment.
1. The 3-digit puzzle
In this assignment, you will implement a number of search algorithms to solve the 3-digit puzzle.
Given are two 3-digit numbers called (start) and (goal) and also a set of 3-digit numbers called
. To solve the puzzle, we want to get from to in the smallest number of moves. A move is a
transformation of one number into another number by adding or subtracting 1 to one of its digits. For
example, a move can take you from 123 to 124 by adding 1 to the last digit or from 953 to 853 by subtracting
1 from the first digit. Moves must satisfy the following constraints:
1. You cannot add to the digit 9 or subtract from the digit 0;
2. You cannot make a move that transforms the current number into one of the forbidden numbers;
3. You cannot change the same digit twice in two successive moves.
Note that since the numbers have 3 digits, at the beginning there are at most 6 possible moves from . After
the first move, the branching factor is at most 4, due to the constraints on the moves and especially due to
constraint 3.
For the purpose of this assignment numbers starting with 0, e.g. 018, are considered 3-digit numbers.
COMP3308 – Introduction to Artificial Intelligence Semester 1, 2021
Page 2 of 5
2. Tasks
1. Write a program to find a solution of the puzzle using the following 6 search strategies: BFS, DFS, IDS,
Greedy, A* and Hill-climbing. Use the Manhattan heuristic as a heuristic for A* and Greedy and also
as the evaluation function in Hill-climbing.
The Manhattan heuristic for a move between two numbers A and B is the sum of the absolute
differences of the corresponding digits of these numbers, e.g. ℎ(123, 492) = |1 − 4| + |2 − 9| +
|3 − 2| = 11.