SE250:lab-X:jpar277

Overview

So to start off, I had to follow the instructions provided by rwan - at 1:30am !!! It worked fine after that.

In the search.c file, the init states were set for a puzzle of size 4x4 when infact we're dealing with a puzzle of size 3x3, so by deleting the inputs 9-f we get a program which actually runs!

Task1

There are 8 different pieces to the puzzle, 9 if you include the empty space. There are 9 different places in which you can place each piece and order does matter. So to find the number of different states you go 9P9 or 9! = 362880 different states.

As for the number of edges, this is a lot harder to work out, having said that, we only need to make an estimate as stated in the handout. So there are 2, 3 or 4 links between a state. The corners have 2 links, the sides have 3 links and the middle has 4 links. This leads to 2*4+3*4+4 = 24. If we count all the links we will have counted them twice as you would go from one state to another but then count the link to return to the previous state. So the calculation is 24/9*9!/2 = 483840 edges.

Task2

A summary of the algorithm.

Initialise the start and goal states.
Initialise the StateList
Call the search function
The search function uses a stack to keep track of the previous states.
If the state is the same as the goal state, then end the search and return true.
Otherwise, it looks at its children, the next possible states.
If we haven't seen the child state before, then it adds it to the stack.
Then it releases the children and looks at the children of those children.
If the search function returns true then print the list of states to get to the solution. Otherwise print "Cannot solve\n"

The states visited variable takes note of the states that you have looked at, not the number of states changed in order to reach the goal.

Task3

So we had to draw this by hand but I did it in paint w00~! ><

Task4

Where do we call the print_state function?! :S

Task5

Task6

Task7

The Depth First Search visited 13135 different states.

Task8

Task9

To avoid going in an infinite loop of visited states, it keeps track of the previously visited states so that it doesn't go around in a circle.

It uses a hash table to keep track of the data. Or an array. I'm not quite sure I got lost in the piles of code - so many header files to go through, one file leads to another @_@!