Question 7
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