SE250:lab-X:sdal039

Task 1

Number of states for the 8 puzzle : 9! (362880)

Number of edges : 483840 The number of edges was found like this: 4 of the squares have two possible moves, 4 of the squares have 3 possible moves and 1 square has 4 possible moves. So the average number of edges between nodes is 8/9 + 12/9 + 4/9. Multiplied by 9!, and dividing by 2 to remove the edges that go in the opposite direction gives the above number.

Task 2

Search algorithm: While there is another state left to check, pop first state from the state list into a temporary variable. Compare this with the goal state and, if equal, set success Boolean equal to true and end loop. If not equal then get the children of the temporary state, add them to the set of states to iterate through, add the current state to the list of visited states and repeat loop.

Task 3

Here's a pic of what the graph looks like. It's too small to see the numbers, but it's probably more helpful than the really really big PDF version. [Image: http://img232.imageshack.us/my.php?image=56721164uz4.gif]

Task 4

The search code appears to be going depth-first down the left most (minimum) path first. Fortunately the solution happened to be on this path so it was quick to find.

Task 5

Found it in 5 states.

Task 6

I think it's something to do with the pop function. It takes off the minimum node from the tree, but we want it to take off the left most node on the bottom most level. This will result in all children of same depth being searched before moving down to the next level.

Task 7

For initial state '5674.8321', depth first: 35139 states, cannot solve.

For initial state '1238.4765', depth first: 40036 states, cannot solve.