Question 5
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.
What is true about the gameboard state space?
(Note: a path is a sequence of one or more moves.)
At least one state has no path from another state.
Every state has a path to every other state.
Every state has at most two neighbours.
Every state has at least 12 neighbours.