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