CS 367: Tutorial Week 1 – updated problems

Please bring worked solutions to tutorial to go over with the tutors in tutorial.
You will learn much more if you try them on your own first.

Q1: Towers of Hanoi

The Towers of Hanoi is a famous problem for studying recursion in computer science and recurrence equations
in discrete mathematics. We start with N discs of varying sizes on a peg (stacked in order according to size),
and two empty pegs. We are allowed to move a disc from one peg to another, but we are never allowed to move
a larger disc on top of a smaller disc. The goal is to move all the discs to the rightmost peg (see figure).

In this problem, we will formulate the Towers of Hanoi as a search problem.

(a) Propose a state representation for the problem

One possible state representation would be to store three lists, corresponding to which discs are on which peg.
If we assume that the N discs are numbered in order of increasing size 1, ..., n, then we can represent each peg
as an ordered list of integers corresponding to which discs are on that peg.

(b) What is the size of the state space?

If there are k pegs and n disks, then the size of the state space is kn.For this setup, the size is 3N .

(c) What is the start state?

([1, ..., n], [], [])

(d) From a given state, what actions are legal?

We can pop the first integer from any list (i.e., peg) and push it onto the front of another list (peg), so long as
it is smaller than the integer currently at the front of the list being pushed to (i.e., peg being moved to).

(e) What is the goal test?

Is the state the same as ([], [], [1, ..., n])?

1
 Q2: Search algorithms in action

For each of the following tree search strategies, work out the order in which states are expanded, as well as
the path returned by the tree search. In all cases, assume ties resolve in such a way that states with earlier
alphabetical order are expanded first. Remember that in graph search, a state is expanded only once.

a) Depth-first search.
States Expanded: Start, A, C, D, Goal
Path Returned: Start-A-C-D-Goal

b) Breadth-first search.
States Expanded: Start, A, B, D, C, Goal
Path Returned: Start-D-Goal

c) Iterative Deepening search.

States Expanded: Start, Start, A, B, D, Start, A, C, B, D, D, C, Goal
Path Returned: Start-D-Goal

d) Uniform cost search.

States Expanded: Start, A, B, D, C, Goal
Path Returned: Start-A-C-Goal
2
Q3: More Search Algorithms
Consider the following tree. Apply BFS, DFS and ID starting from the node 1 and search for the target node (labeled by
14). Suppose that when the search has multiple directions, it will always choose the direction that has the least index.
Illustrate the search tree generated by the algorithms.

BFS
States Expanded: 1,2,3,4,5,6,7,8,9,10,11,12,13,14
Path Returned: 1,3,7,14

DFS
States Expanded: 1,2,4,8,15,23,16,24,25,9,5,10,17,18,26,27,11,6,12,19,20,28,29,7,13,14
Path Returned: 1,3,7,14

ID
States Expanded: 1,1,2,3, 1,2,4,5,3,6,7,1,2,4,8,9,5,10,11,6,12,7,13,14
Path Returned: 1,3,7,14

3
Q4: UCS Algorithm
A tourist wants to drive from Bucharest to Arad. The map is shown in the figure below. Describe the process of applying
UCS. You can use a graph search and duplicates do not need to be expanded.

Nodes Expanded: Bucharest, Urziceni, Pitesti, Hirsova, Rimnicu Vilcea, Fagaras, Vaslui, Craiova, Sibiu, Iasi, Drobeta,
Arad (picked but not expanded)
Path: Bucharest => Pitesti => Rimnicu Vilcea => Sibiu => Arad

Bucharest => Urziceni (85)

Bucharest => Giurgiu (90)
Bucharest => Pitesti (101)
Bucharest => Fagaras (211)
Bucharest => Urziceni => Hirsova (183)
Bucharest => Urziceni => Vaslui (227)
Bucharest => Pitesti => Rimnicu Vilcea (198)
Bucharest => Pitesti => Craiova (239)
Bucharest => Urziceni => Hirsova => Eforie (269)
Bucharest => Pitesti => Rimnicu Vilcea => Sibiu (278)
Bucharest => Pitesti => Rimnicu Vilcea => Craiova (344)
Bucharest => Fagaras => Sibiu (310)
Bucharest => Urziceni => Vaslui => Iasi (319)
Bucharest => Pitesti => Craiova => Drobeta (359)
Bucharest => Pitesti => Rimnicu Vilcea => Sibiu => Arad (418)
Bucharest => Pitesti => Rimnicu Vilcea => Sibiu => Oradea (429)
Bucharest => Urziceni => Vaslui => Iasi => Neamt (406)
Bucharest => Pitesti => Craiova => Drobeta => Mehadia (434)
Bucharest => Pitesti => Rimnicu Vilcea => Sibiu => Arad => Stop

4
 Q5: Pacman’s Life (extra for experts)
Suppose a maze has height M and width N and there are F food pellets at the beginning. Pacman can move
North, South, Eastor West in the maze.

(a) In this subquestion, the position of Pacman is known, and he wants to pick up all F food pellets in the
maze. However, Pacman can move North at most two times overall.
What is the size of a minimal state space for this problem? Give your answer as a product of terms that reference
problem quantities such as (but not limited to) M, N, F , etc. Below each term, state the information it encodes.
For example, youmight write 4 × MN and write number of directions underneath the first term and Pacman’s
position under the second.

MN × 2F × 3. Pacman’s position, a boolean vector representing whether a certain food pellet has been eaten, and
the number of times Pacman has moved North (which could be 0, 1 or 2).

(b) In this subquestion, Pacman is lost in the maze, and does not know his location. However, Pacman still
wants to visit every single square (he does not care about collecting the food pellets any more). Pacman’s
task is to find a sequence of actions which guarantees that he will visit every single square.
What is the size of a minimal state space for this problem? As in part(a), give your answer as a product of
terms alongwith the information encoded by each term. You will receive partial credit for a complete but non-
minimal state space.

(MN)MN x 2MNxMN. For every pair of starting location and current location, you need a grid of all visited
locations.

To figure out the size of the minimal state space we need to figure out what is the content of the smallest state that allows
us to solve the original problem. To handle the lack of information about pacman’s location, we need to keep track of where
he could be currently (so that we know what will be true after the next action). Notice that this specific question does not
require that our state enable pacman to find the shortest possible path just that our state representation enables him to find
a solution. At least that is how I am interpreting this question. My proposal is to keep a separate “board” for each possible
location (i.e., each non-wall/barrier location). A board needs to have to 2 specific bits of information, which squares have
been visited and where pacman is now. The “visited” info is a Boolean vector of M x N and could have 2**M x N possible
values (it could actually be a bit smaller than that if we numbered all the non-wall squares and use that to designate
locations, but probably not worth it because then we’d need to record which locations are connected to which other
ones). Pacman’s current location can only be 1 of M x N values. So the total number of values for a board is M x N x (2**M
x N).

Let us assume that we want to answer this question for just 3 possible start locations, then each state would need to have
(MxN x 2**MxN)x(MxN x 2**MxN)x(MxN x 2**MxN) which would be ((MxN)**3 x 2**(3xMxN)).

But the question doesn’t say 3, it says any number so that should be any location.
So, now the question is how many boards are there? Since initially the squares are all unvisited except for where pacman
is initially located, there must be a board for every one of the M x N positions (we are ignoring that some of the locations
have a wall and therefore pacman cannot be standing there). So, theoretically each board is independent of every other
board, so the total number of states is: (M x N)**(M x N) x (2 ** ((M x N)x(M x N))).

5
Q6. More Search (extra for experts)
Consider the following problem setup:
The head TA is figuring out the discussion schedule. We have M TAs and N discussion sections. Each
discussion section has a known time slot, and fortunately, at most 2 discussions are in the same time slot. In
the N discussion sections, we need exactly K of them to be exam prep sections, and the rest to be normal
sections.
We also want the following conditions to hold:

• We would like to have exactly one TA for each discussion section.

• A TA cannot be teaching 2 discussion at the same time slot.
• Some TAs do not teach regular discussions, some do not teach exam prep, and others can teach either.
• If two discussions are in the same time slot, we also don’t want them to be the same type of discussion
for the sake of best allocation of resources.

(a) Cast this as a search problem. Specifically, appropriately define the state representation, the successor
function, the start state and the goal test.

State representation:
A state is simply a vector that shows which TAs are allocated to which discussion section. There are N discussion
sections and M TAs, so the vector has N elements, and each element can have at most one TA assigned.
We assume that there is a lot of information that is statically encoded, e.g., what type of discussion is associated with a
discussion section, when that discussion section happens (what time slot), what types of discusssions a TA is capable of
handling, etc. But these do not change through the problem solving process.

Successor function:
The effect of the action is to assign one TA to one discussion section.
The preconditions are:
- No one is already assigned to that discussion section.
- The TA is capable of handling that type of discussion.
- The TA is not already teaching a discussion section at the same time as this discussion section.

Start state:
No discussion section has a TA assigned yet

Goal test:
All discussions sections have a TA assigned

(b) Calculate the state space size and the branching factor of the search tree, then suggest a search algorithm
to tackle the problem. If you are using DFS/BFS, explain your choice of algorithm in a paragraph. If you
are using UCS/Greedy/A* search, please define in a paragraph what cost function and/or heuristic is
being used. It doesn’t necessarily need to be a rigorous definition but more of a qualitative description of
whatthe cost function/heuristic does.

State space size: M N

6
 Branching factor: If at each iteration both the discussion section and the TA have to be chosen then the branching factor is M x N,
but if the search starts by assigning a TA to the first discussion section and each iteration works on a TA to the next discussion section
then the branching factor is just M We assume that the latter is being done, i.e., we just sequentially assign TAs to
discussion sections!!

Proposed search algorithm: I would pick DFS

Explanation:
because the state space size is potentially much much larger than available memory unless we had a very good
heuristic. Also, all solution paths are optimal, i.e., N TA assignments and if we not to worry about duplicate
states, every path will lead to a unique schedule. In short, graph-based approaches are likely to run out of
memory and the normal drawbacks of DFS are applicable to this problem.

Q7:
Your goal is to navigate a robot out of a maze. The robot starts in the center of the maze
facing north. You can turn the robot to face north, east, south, or west. You can direct the
robot to move forward a certain distance, although it will stop before hitting a wall.

a. Formulate this problem. How large is the state space?

We’ll define the coordinate system so that the center of the maze is at (0, 0), and the maze itself is a square
from (−1,−1) to (1, 1).
Initial state: robot at coordinate (0, 0), facing North.
Goal test: either |x| > 1 or |y| > 1 where (x, y) is the current location.
Successor function: move forwards any distance d; change direction robot it facing.
Cost function: total distance moved.
The state space is infinitely large, since the robot’s position is continuous.

b. In navigating a maze, the only place we need to turn is at the intersection of two or more corridors.
Reformulate this problem using this observation. How large is the state space now?
The state will record the intersection the robot is currently at, along with the direction
it’s facing. At the end of each corridor leaving the maze we will have an exit node.
We’ll assume some node corresponds to the center of the maze.
Initial state: at the center of the maze facing North.
Goal test: at an exit node.
Successor function: move to the next intersection in front of us, if there is one; turn to face a new direction.
Cost function: total distance moved.
There are 4n states, where n is the number of intersections.

c. From each point in the maze, we can move in any of the four directions until we reach a turning point,
and this is the only action we need to do. Reformulate the problem using these actions. Do we need to
keep track of the robot’s orientation now?
Initial state: at the center of the maze.
Goal test: at an exit node.
Successor function: move to next intersection to the North, South, East, or West.
Cost function: total distance moved.
7
 We no longer need to keep track of the robot’s orientation since it is irrelevant topredicting the outcome of
our actions, and not part of the goal test. The motor system
that executes this plan will need to keep track of the robot’s current orientation, to know
when to rotate the robot.

d. In our initial description of the problem we already abstracted from the real world, restricting actions
and removing details. List three such simplifications we made.
State abstractions:
(i) Ignoring the height of the robot off the ground, whether it is tilted off the vertical.
(ii) The robot can face in only four directions.
(iii) Other parts of the world ignored: possibility of other robots in the maze, the
weather in the Caribbean.
Action abstractions:
(i) We assumed all positions we safely accessible: the robot couldn’t get stuck or
damaged.
(ii) The robot can move as far as it wants, without having to recharge its batteries.
(iii) Simplified movement system: moving forwards a certain distance, rather than controlled
each individual motor and watching the sensors to detect collisions.

Q8:
Give a complete problem formulation for each of the following. Choose a formulation
that is precise enough to be implemented.

a. Using only four colors, you have to color a planar map in such a way that no two adjacent regions have
the same color.
Initial state: Noregions colored.
Goal test: All regions colored, and no two adjacent regions have the same color.
Successor function: Assign a color to a region.
Cost function: Number of assignments.

b. A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He
would like to get the bananas. The room contains two stackable, movable, climbable 3-foot-high crates.
Initial state: Asdescribed in the text.
Goal test: Monkey has bananas.
Successor function: Hop on crate; Hop off crate; Push crate from one spot to another;
Walk from one spot to another; grab bananas (if standing on crate).
Cost function: Number of actions.

c. You have a program that outputs the message “illegal input record” when fed a certain file of input
records. You know that processing of each record is independent of the other records. You want to
discover what record is illegal.
Initial state: considering all input records.
Goal test: considering a single record, and it gives “illegal input” message.
Successor function: run again on the first half of the records; run again on the second
half of the records.
Cost function: Number of runs.
Note: This is a contingency problem; you need to see whether a run gives an error
message or not to decide what to do next.

8
 d. You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the
jugs up or empty them out from one to another or onto the ground. You need to measure out exactly
one gallon.

Initial state: jugs have values [0, 0, 0].

Successor function: given values [x, y, z], generate [12, y, z], [x, 8, z], [x, y, 3] (by filling);
[0, y, z], [x, 0, z], [x, y, 0] (by emptying); or for any two jugs with current values
x and y, pour y into x; this changes the jug with x to the minimum of x + y and the
capacity of the jug, and decrements the jug with y by by the amount gained by the first jug.
Cost function: Number of actions.

Q9
The missionaries and cannibals problem is usually stated as follows. Three missionaries
and three cannibals are on one side of a river, along with a boat that can hold one or
two people. Find a way to get everyone to the other side without ever leaving a group of missionaries
in one place outnumbered by the cannibals in that place. This problem is famous in
AI because it was the subject of the first paper that approached problem formulation from an
analytical viewpoint (Amarel, 1968).

a. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution.
Draw a diagram of the complete state space.

b. Implement and solve the problem optimally using an appropriate search algorithm. Is it a good idea to
check for repeated states?
c. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?

a. Here is one possible representation: Astate is a six-tuple of integers listing the number
of missionaries, cannibals, and boats on the first side, and then the second side of the
river. The goal is a state with 3 missionaries and 3 cannibals on the second side. The
cost function is one per action, and the successors of a state are all the states that move
1 or 2 people and 1 boat fromone side to another.

b. The search space is small, so any optimal algorithm works. For an example, see the
file "search/domains/cannibals.lisp". It suffices to eliminate moves that
circle back to the state just visited. From all but the first and last states, there is only
one other choice.

c. It is not obvious that almost allmoves are either illegal or revert to the previous state.
9
There is a feeling of a large branching factor, and no clear way to proceed.

Q10
Consider a state space where the start state is number 1 and each state k has two
successors: numbers 2k and 2k + 1.

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth first search, depth-
limited search with limit 3, and iterative deepening search.

c. How well would bidirectional search work on this problem? What is the branching factor in each
direction of the bidirectional search?

d. Does the answer to (c) suggest a reformulation of the problem that would allow you to solve the
problem of getting from state 1 to a given goal state with almost no search?

e. Call the action going from k to 2k Left, and the action going to 2k + 1 Right. Can you find an algorithm
that outputs the solution to this problem without any search at all?

2 3

4 5 6 7

8 9 10 11 12 13 14 15

Figure 1: The state space for the problem defined in Question 10.

a. See Figure 1.
b. Breadth-first: 1 2 3 4 5 6 7 8 9 10 11
Depth-limited: 1 2 4 8 9 5 10 11
Iterative deepening: 1; 1 2 3; 1 2 4 5 3 6 7; 1 2 4 8 9 5 10 11
c. Bidirectional search isveryuseful, because theonly successor of n in the reverse direction
is ⌊(n/2)⌋. This helps focus the search. The branching factor is 2 in the forward
direction; 1 in the reverse direction.
23
d. Yes; start at the goal, and apply the single reverse successor action until you reach 1.
e. The solution can be read off the binary numeral for the goal number. Write the goal
number in binary. Since we can only reach positive integers, this binary expansion
beings with a 1. From most- to least- significant bit, skipping the initial 1, go Left to
the node 2n if this bit is 0 and go Right to node 2n + 1 if it is 1. For example, suppose
the goal is 11, which is 1011 in binary. The solution is therefore Left, Right, Right.
10
11