AI: Search Methods for Problem Solving Quiz 1: 15 March 2026 (January 2026 term)

STATE SPACE SEARCH
Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.

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

STATE SPACE SEARCH
Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.

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

STATE SPACE SEARCH
Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.

d(G,D) 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
Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.

Select the true statement about knight moves in the given state space.

STATE SPACE SEARCH
Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.

Select the true statements about the given state space.

STATE SPACE SEARCH
Background: On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.

In the given state space, is it possible for a knight to start from a position and visit the remaining positions exactly once and return to the starting position to form a knight’s tour?

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the OPEN or CLOSED list.
Based on the above data, answer the given subquestions.

List the first 4 positions inspected by Hill Climbing. 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

SEARCH
Background:
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite corner of that rectangle and there are eight possible jumps (moves) for a knight.

Problem Statement:
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.

From an allowable position, a knight can jump over obstacles and land on another allowable position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard. Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
Note: when we say a node (or a position) is inspected/expanded/refined it means: the node (or position) 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 the neighbours that are already present in the 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: A,B,C,D Answers Case Sensitive : No

Algorithms
Based on the topic, answer the given subquestions.

Which of the following algorithms are designed to escape local minima?

Algorithms
Based on the topic, answer the given subquestions.

Stochastic Hill Climbing decides whether to move from N to a randomly selected neighbour x based on the probability function P = 1/(1+e^(-deltaE/T)), where T is a non negative temperature parameter, and deltaE = eval(x) - eval(N) for maximization problems where a positive deltaE indicates that x is better than N. Select the correct statement(s).

Algorithms
Based on the topic, answer the given subquestions.

What is the total number of tours possible for 4 cities?
Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 17

Algorithms
Based on the topic, answer the given subquestions.

Given a 4-city tour as input, how many unique tours (unique neighbours) will be generated by a MoveGen using the 2-city exchange operator?
Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 17

TSP
Use the distance matrix (and the sorted edge list) to construct TSP tours.

Based on the above data, answer the given subquestions.

Construct a tour using Greedy Heuristic. Enter the path representation of the tour starting from “A”.
Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z Answers Case Sensitive : No

TSP
Use the distance matrix (and the sorted edge list) to construct TSP tours.

Based on the above data, answer the given subquestions.

Use city “A” as the fulcrum (base) node and complete the given savings list then construct the Savings tour. Enter the path representation of the tour starting from “A”.

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

TSP
Use the distance matrix (and the sorted edge list) to construct TSP tours.

Based on the above data, answer the given subquestions.

What is the cost of the tour generated by Savings Heuristic?
Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: 17

TSP
Use the distance matrix (and the sorted edge list) to construct TSP tours.

Based on the above data, answer the given subquestions.

Consider N cities on the Euclidean plane, how many merge operations will be performed while constructing the Savings tour?
Enter an expression in the textbox. Answer format: 2x^2 - 3x + 1 Answers Case Sensitive : No

TSP
Use the distance matrix (and the sorted edge list) to construct TSP tours.

Based on the above data, answer the given subquestions.

Consider N cities on the Euclidean plane, for each city, begin at that city and compute a tour using Nearest Neighbour Heuristic. From the resulting N tours, select the cheapest tour. What can you conclude about the procedure?