SE250:lab-X:ssre005

1. Calculation of no. of states in State Space Graph and estimate of number of edges:

9! different possible states.

No. of edges from each state depends on the location of the space in the puzzle. If the Space is in the middle then 4 different legal moves are available and thus 4 edges will come from this state node. If the Space is on either of the 4 squares adjacent to the centre square then 3 different edges will come from this state. If the Space is on either of the 4 corners then 2 different edges will come from this state node.

Thus since 9!/9 = 8! states have the empty space in the centre, (9!/9)*4 = 8!*4 states have a space in either of the 4 squares adjacent to the centre and (9!/9)*4 = 8!*4 states have a space in either of the 4 corners:

The total number of edges in the State Space Graph should be:

(8!)*4 + (8!*4)*3 + (8!*4)*2.

Where the coefficients (*4, *3 and *2) account for the number of legal moves available for each of these states.

This is however incorrect as it does not take into account "double edges" where legal moves exist both ways for two states and thus a "double edge" can be draw between the states rather than two individual edges as suggested by my answer.

Mark suggested that the solution to this problem would be to divide my answer by 2.

2.

Looks way too tedious. Might come back to this later.

3.

Drew my graph and included double edges. Trying to figure out how to run the actual program.