SE250:lab-X:jsmi233

1. Calculate how many different states exist for the 8-piece puzzle. Estimate the number of edges in the complete state space graph. Explain how you made these calculations in your report.

The number of different states is 9! This is because any of the nine values can go in the first position, then and of the remaining 8 can go in the second position etc.

The number of edges connected to a node that has the blank tile in a corner is 2. The number of edges connected to a node that has the blank tile in the centre is 4. This covers all the edges. When the position of the blank tile is fixed, there are 8! possible arrangements of the remaining values. Hence the total number of edges is 8! * 2 * 4 + 8! * 4 = 8! * 12

2. The main search code can be found in search.c. In your own words, write a summary of the search algorithm in your report.

The algorithm is a best first search. It adds the neighbouring states to a tree which is sorted using the Manhattan distance. The next state to examine is the minimum node of the tree which will be the state with the smallest Manhattan distance.

4. The search strategy used in search.c is depth first search. Use the print state function to print the first few states the search code checks, compare this to your graph and describe in your own words how this search strategy traverses the search space.

As far as I know, this code does not demonstrate a depth first search, rather a best first search. I think I did task 2 wrong because what I wrote there actually answers this question.

5. Run the search code. What do you notice about the solution compared with the solution in your state graph?

123456.78 ->1234567.8 ->12345678. ->Visited 5 states

If I was doing this manually I would do the same thing, but without the two extra states being visited.

9. How are infinite loops (such as moving a piece back and forth) prevented in the supplied code? What data structures are used?

Here is a code excert:

if( add_to_StateSet( &visited, &cs[ i ] ) )

The stateSet (which is actually a hashtable) is used to store all the nodes that have been visited. If add_to_StateSet returns false, it means the state had previously been added to the hashtable, and hence has already been visited. This allows the algorithm to analyse only those states which have not already been visited.