General Info
You must read fully and carefully the assignment specification and instructions.
Course: COMP20003 Algorithms and Data Structures @ Semester 2, 2025
Deadline Submission: Friday 24th October 2025 @ 5pm (end of Week 12)
Course Weight: 15%
Assignment type: individual
ILOs covered: 2, 4
Submission method: via ED
Purpose
The purpose of this assignment is for you to:
Increase your proficiency in C programming, your dexterity with dynamic memory allocation
and your understanding of data structures, through programming a search algorithm over
Graphs.
Gain experience with applications of graphs and graph algorithms to solving combinatorial
games, one form of artificial intelligence.
Impassable Gate Intro
In this programming assignment, you’ll be expected to build an AI algorithm to solve puzzles
inspired by the Professor Layton and the Lost Future puzzle, Impassable Gate. The puzzle, created
by Akira Tago, asks the player to move the protagonists (the grey block), to the goal position at
the top of the board. The game counts a move as anywhere a piece can slide to unhindered by any
other piece. You can see how this works by looking at the step-by-step solution on the Wiki. The
game can also be found on the Nintendo DS and on mobile devices.
The code in this assignment was adapted from the open-source terminal version of the classic
puzzle game, Sokoban using ncurses made available by CorrentinB.
Game Rules
The game is played on a board of squares, where each square is open space or a wall. Some
open spaces contain parts of pieces, and the Professor Layton and Little Luke piece will always be
on the board. In the simplified AI approach we use, each movement is limited to a single
direction, rather than any open space. Each piece takes up multiple spaces on the board, and all
parts of a piece must move together. If any part of a piece cannot move in the direction (i.e. a
piece already occupies the location, or there is a wall) then no part of the piece can move.
For simplicity of implementation, the Professor Layton and Little Luke piece is always numbered
as piece 0. The pieces are confined to the board, and the goal is always the same size and shape
as the Professor Layton and Little Luke piece. Like the original puzzles, only one goal location is
given.
Puzzle Solution (DS)
An example of solving the first Impassable Gate puzzle is shown in this playthrough:
For the curious puzzle solver
The Science of Impassable Gate
Like a number of puzzles, the problem of finding the shortest Impassable Gate solution can be
formulated as a decision problem. In simple terms, for a given puzzle, we can ask if a solution
exists in kk or fewer steps, we can then - in polynomial time - check that a solution of kk or fewer
steps is a valid solution (i.e. that each move made is valid and that the final state solves the
problem).
NP-complete problems are hard to solve. The best algorithms to solve NP-Complete problems run
in exponential time as a function of the size of the problem and the shortest accepted
solution. Hence, be aware that your AI solver may struggle more as the number of pieces and size
of the board increases. We talked in the lectures about the Travelling Salesman Problem as one
example of an NP-Complete problem. In fact, many real-world problems fall under this category.
We are going to learn more about NP-Complete problems in the last lecture of the course via an
invited talk in week 12.
Interestingly, the naïve approach (Algorithm 1), for a puzzle with nn pieces and kk steps, is
O((4n)k)O((4n)k). The duplicate checking algorithm (Algorithm 2) mostly replicates this worst-case
bound (O((3+4(n−1))k)O((3+4(n−1))k)) for an unbounded sized board, but will be much more
powerful as it avoids re-exploring seen states, and avoids returning to the immediate prior state -
for a bounded board, each board square could potentially have one of each piece, so at most we
would see, with qq being the number of open squares on the board, O(nq)O(n**q) states. The
novelty checking algorithm (Algorithm 3) improves this significantly, reducing the complexity to
O(nqw)O(nqw), where ww is the width of the search. Algorithm 3's worst case (in this puzzle)
happens when the solution is not found until w=nw=n, which leads to O(nq+1)O(n**q+1)
complexity due to re-exploring the puzzle ww times.
References:
Images from HD remake gameplay.
Graph = <V, E> implicit graph
unweighted, directed
########
###GG###
###HH###
# 00 #
## ##
# #
# #
# #
# #
########
########
###HH###
###HH###
# #
## ##
# #
# #
# #
# #
########
########
###GG###
###GG###
# 00 #
## 00 ##
# #
# #
# #
# #
########
dfs
Iterated Width (IW) Search
Iterative Deepening is a search algorithm that works similarly to depth-first search, but with a
small change, whenever we reach the current depth limit, the search does not generate any
successors (next moves). Once no more search nodes are generated, the search stops and we
increase the depth limit by one, then repeat the search from the start.
Iterated Width Search is a search algorithm that works similarly to breadth-first search, but any
node which is reached which has been seen before does not generate any successors. A more
nuanced version of "seen before", known as novelty, is how this algorithm makes its gains. For
this algorithm, any node which has a higher novelty rank than the current *width* limit of the
search does not generate any successors. A state which has been fully seen before has
maximum novelty rank. Once no more search nodes are generated, the search stops and we
increase the *width* by one, then repeat the search.
Iterated Width (IW) search
The novelty of a state is the size of the smallest combination of atoms that have been true
together for the first time. For example:
seen: {(2,2,3)}, {(1,3,2)}
{(2,2,3), (1,3,2)}
If at(1,3,2) has never been true until this state, the novelty is 1 , because we only need to
look at one atom to see something we haven't seen before.
If the piece 1 has been at (3,2) and the piece 2 has been at (2,3) separately before, but
piece 1 has never been at (3,2) with piece 2 at (2,3) before, then the novelty is 2 ,
because we need to look at this combination of two atoms to see something we haven't
seen before.
If at(1,3,2) , at(2,2,3) and at(3,3,3) are all true in a given state, and all combinations
of those pairs (i.e. at(1,3,2) and at(2,2,3) , at(1,3,2) and at(3,3,3) , at(2,2,3) and
at(3,3,3) ) have been true in previous states, but this state is the first time we've seen these
three atoms true together, then the novelty is 3 , because we need to look at this
combination of three atoms to see something we haven't seen before.
In Iterated Width (IW) search, we start at width 1 (referred to as IW(1)), and then increase the
width after the search generates no new nodes and restart from the root. The maximum novelty
of a state is the maximum number of atoms that can be true in any state + 1. This value is
assigned to a state if all its combination of atoms have been seen before in the search. When the
maximum width k = max number of atoms is used, **IW(k)** becomes a breadth first search
of the full problem with duplicate states excluded.
To see the advantage of novelty, let's consider a puzzle:
In this puzzle, assume we can slide the red and yellow square, and we want to reach the green
square. Looking at the first level of the novelty 1 search tree, we see it runs the same way as
breadth first search:
But we see a difference on the next level. We look first at the left node (where red has moved left),
three moves are generated:
Yellow moves right - this state is eliminated because we have seen the yellow block in the
second column before (on the first level). In particular, it has novelty 2, because we need to
look at the position of the red and yellow block to see something new.
Red moves left - this state is eliminated because we have seen the yellow block in this
column, and the red block in this column (in the zeroth level). In particular, it has novelty 3
(assuming we only have 2 atoms in a state), because we have seen this state in its
entirety before.
Red moves right - this state remains because we have not seen the red block in the third
column before. In particular, it has novelty 1, the current width of the search.
Completing this level of the tree, two new states are retained in the search, similarly from the right
node:
level 0: [(R,0,0), (Y,1,0)]
level 1: [(R,0,1), (Y,1,0)], [(R,0,0), (Y,1,1)]
level 2: [(R,0,2), (Y,1,0)], [(R,0,0), (Y,1,0)],[(R,0,1), (Y,1,1)], [(R,0,1),
(Y,1,1)], [(R,0,0), (Y,1,2)], [(R,0,0), (Y,1,0)]
level 3: ...................................
w=1
seen:
size = 1 {(R,0,0)}, {(Y,1,0)}, {(R,0,1)}, {(Y,1,1)}, {R,0,2}
Assessment:
Solver (finds solutions for capability test cases) [4
marks]
[0.5 marks] ILO 4 – Able to find solutions that require moving from the starting location (test
case 1)
[0.5 marks] ILO 4 – Able to find solutions that require more than one state exploration (test
case 2)
[0.5 marks] ILO 4 – Able to find solutions to single l/r moves (test case 3)
[0.5 marks] ILO 4 – Able to find each single move solution (u,d,l,r) (test case 4)
[0.5 marks] ILO 4 – Able to find a 2-move solution if the same move is made (test case 5)
[0.5 marks] ILO 4 – Able to find 2-move solutions (up to test case 7)
[0.5 marks] ILO 4 - Able to move pieces out of the way, but may not be able to handle extra
pieces that don't need to move (up to test case 9)
[0.5 marks] ILO 4 - Able to solve puzzles even when it is necessary to move pieces out of the
way (all test cases)
These all involve the implementation of given algorithms. It is necessary to utilise the radix tree
data structure to implement the novelty-based search, though its implementation isn't assessed in
this assignment.
Memory correctly freed [1 mark]
[0.5 marks] ILO4 - Able to free memory of growing memory usage elements (i.e. states) in the
context of implementing a given algorithm.
[0.5 marks] ILO4 - Able to free memory of constant memory usage elements (e.g. initial state
data, etc.) in the context of implementing a given algorithm.
These all involve adding to the given algorithm to handle the return of memory once it is no longer
needed, in the context of this problem, this is likely necessary to achieve puzzle solving under the
more challenging memory constraints of Ed.
Memory is free of errors [1 mark]
[0.5 marks] ILO4 - Able to implement the given algorithm in C for solving the puzzles without
significant enough errors to affect the output.
[0.5 marks] ILO4 - Able to implement the given algorithm in C for solving the puzzles, applying
a systematic approach to eliminate all errors detectable through Valgrind memory checking.
These all involve the implementation of the given algorithm. A number of minor errors might
appear that don't affect the output, this set of standards is meant to capture your ability to resolve
those errors.
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
