Question 2
STATE SPACE SEARCH
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take two steps in a chosen direction, turn 60 degrees left or right, and take one final step; or equivalently take one step in a chosen direction, turn 60 degrees left or right, and take two final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
Problem Statement:
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
The number of unique states in the gameboard state space is __________ .
Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: 42