AI: Search Methods for Problem Solving Quiz 1: 13 July 2025 (May 2025 term)

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

Which of the following will be present in MoveGen(411)?

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

h(411) is equal to __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 7

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

For the state space Graph-123, the lowest value of h is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 7

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

For the state space Graph-123, the highest value of h is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 7

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

For the state space Graph-123, the heuristic function h defines a __________ .

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

Select the statements that are true in the state space Graph-123.

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

In the state space Graph-123, __________ .

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

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

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

Use Depth-First Search to find a path from “123” to “600” where the MoveGen function returns neighbours in ascending order. At the point when GoalTest returns true, the goal state will be present in the OPEN list, what other states will be present in the OPEN list at that point? Enter the states in ascending order as a comma separated list.
Enter NIL if no other states are present in OPEN.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 123,204

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

Use Breadth-First Search to find a path from “123” to “600” where the MoveGen function returns neighbours in ascending order. At the point when GoalTest returns true, the goal state will be present in the OPEN list, what other states will be present in the OPEN list at that point? Enter the states in ascending order as a comma separated list.
Enter NIL if no other states are present in OPEN.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 123,204

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

Use Best-First Search to find a path from “123” to “600” where the MoveGen function returns neighbours in ascending order. List the heuristic values of the nodes in the path (from “123” to “600”) discovered by Best-First Search.
Enter the heuristic values as a comma separated list. Enter NIL if no path is found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 2,4,2

STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].

Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.

Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.

For the state space Graph-123, which of the following algorithms will find the shortest path from “123” to “600” when the MoveGen function returns neighbours in ascending order?

Genetic Algorithm
Which of the following are constructive methods?

Genetic Algorithm
Tour representations are basically raw lists (list of city names or list of city positions) which are interpreted differently by each representation. Given a symmetric TSP, for which of the following representations the raw list reversal will produce a new tour?

Genetic Algorithm
Compute the ordinal representation of tour P1 (given in path representation). Use A,B,C,D,E,F as the index sequence.
P1: E,F,A,C,D,B
Enter the ORDINAL representation as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 1,3,5,9,6,4

Genetic Algorithm
Path representation of two parent tours are given below. Express the parent tours in ordinal representation (use A,B,C,D,E,F as the index sequence) and generate offspring using midpoint crossover. Enter the ordinal representation of one of the child tours.
P1: E,F,A,C,D,B
P2: C,A,D,B,E,F
Enter the ordinal representation as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 1,3,5,9,6,4

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

Based on the above data, answer the given subquestions.

Use D as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________ . Enter the path representation of the tour starting from D and in the order the cities are visited by the Nearest Neighbour Heuristic.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

Based on the above data, answer the given subquestions.

What is the cost of the tour generated by Nearest Neighbour Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information 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 city D.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

Based on the above data, answer the given subquestions.

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

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

Based on the above data, answer the given subquestions.

Construct the savings tour using D as the base city. The savings for the pairs AB, AC, BC and BE, respectively, are 61, 70, 48 and 88. Compute the savings for the remaining pairs of cities and then compute the savings tour. Enter the path representation of the savings tour starting from city D. Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: D,X,Y,Z

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

Based on the above data, answer the given subquestions.

For the given TSP, which of the following algorithms produce a better tour?