AI: Search Methods for Problem Solving Quiz 1: 19 July 2026 (May 2026 term)

STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.

A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.

Design a state representation for the gameboard, enter its description in the textbox as succinct as possible. Answers Case Sensitive : No

STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.

A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.

The number of unique states in the gameboard state space is __________ .
Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 42

STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.

A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.

MoveGen(G) is __________ . Enter a comma separated list of positions. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.

A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.

d(C,G) is __________ .
Enter a decimal number rounded to one decimal place. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 42.1

STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.

A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.

What is true about the gameboard state space?
(Note: a path is a sequence of one or more moves.)

STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.

A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.

Can a knight complete a TSP tour on the gameboard, visiting all the positions?

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

List the first 4 positions inspected by Depth-First Search. List the positions in the order they are inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

What is the path found by Depth-First Search?
Enter the path as a comma separated list of positions. Enter NIL if a path to the goal is not found. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

List the first 4 positions inspected by Breadth-First Search. List the positions in the order they are inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

What is the path found by Breadth-First Search?
Enter the path as a comma separated list of positions. Enter NIL if a path to the goal is not found. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

Inscript List the first 4 positions inspected by Best-First Search. List the positions in the order they are inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

What is the path found by Best-First Search?
Enter the path as a comma separated list of positions. Enter NIL if a path to the goal is not found. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

What is the path found by Hill Climbing? Enter the path as a comma separated list of positions. Enter NIL if a path to the goal is not found. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: X,Y,Z Answers Case Sensitive : No

SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.

Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

The heuristic function for the gameboard __________ .

ALGORITHMS
Answer the given subquestions.

Select the formulas that are in Conjunctive Normal Form.

ALGORITHMS
Answer the given subquestions.

Perturbation method(s) used for TSP tour creation is/are __________ .

ALGORITHMS
Answer the given subquestions.

If a genetic algorithm prematurely converges to a homogeneous suboptimal population, then which modification will prevent such convergence?

ALGORITHMS
Answer the given subquestions.

If you initially implement Breadth-First Search using First-In-First-Out Queue and later replace the queue with Max-Priority Queue based on node depth (larger depth equals higher priority), then the memory footprint of the queue would __________ .

ALGORITHMS
Answer the given subquestions.

In the Simulated Annealing schedule, if the temperature parameter T drops to absolute zero very early in the search process, the algorithm will move from the current node N to a random neighbour X __________ .

TSP
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.

Based on the above data, answer the given subquestions.

The given TSP is a __________ . (CAUTION: May require bull work.)

TSP
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.

Based on the above data, answer the given subquestions.

Construct a tour using Nearest Neighbour Heuristic, start from city A. Enter the path representation of the tour in the order it is constructed.
Enter a comma separated list of city names. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y Answers Case Sensitive : No

TSP
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.

Based on the above data, answer the given subquestions.

Use city A as the base (fulcrum) city to complete the savings list then construct the Savings tour. Enter the path representation of the tour starting from city A.

Enter a comma separated list of city names. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y Answers Case Sensitive : No

TSP ALGORITHMS
Answer the given subquestions.

A major drawback of Nearest Neighbour Heuristic for TSP is __________ .

TSP ALGORITHMS
Answer the given subquestions.

What is the core principle used in the Savings Heuristic for TSP?

TSP ALGORITHMS
Answer the given subquestions.

The savings S(a,b) for two cities a and b relative to base/fulcrum city n is __________ , where C(x,y) is the distance between cities x and y.