Question 5
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.
At least one state has no path from another state.
Every state has a path to every other state.
Every state has at most three neighbours.
Every state has eight neighbours.