SE250:lab-X:sshi080
LAB X
Task 1
Different states: 9! = 362880, because there is 9 blocks, e.g. the space can be at 9 different positions, then "1" can be at 8 different positions and so forth
Estimated Edges: Um.. this one is pretty hard, I think:
- 4 different ways when space is in middle
- 3 different ways when space is on the side
- 2 different ways when space is in a corner
Space in the middle, numbers can be different in 8! times, same with others. 8! * 4 + 8! * 3 + *1 * 2?
There are some overlapping here obviously... cbf thinking about it right now :D
Task 2
Some comments would have helped greatly, but I guess that is the point of this task :( This is what I think the algorithm is:
Initialise a start state and a goal state, a list of possible states and the number of states already visited. Call the search function and pass in the start state, goal state, the list of states possible and the number of states already visited. While the ordered state list is not empty: -Pop off the current state from the ordered list of states. -If the current state is the goal state, break loop and record "success" -Otherwise, get the children of the current state. For each children retrieved: -Add to stateset if the child state is not present in the visitedmap -Add to ordered state list Clear the children
Task 3
0 Start: 1 3 Goal: 123456.78 - > 1234567.8 -> 12345678. 1 2 3 1 2 3 1 2 3 4 5 6 - > 4 5 6 -> 4 5 6 . 7 8 7 . 8 7 8 . | 2 123.56478 1 2 3 . 5 6 -> ... 4 7 8
Graph from graph.exe <html> <img src="http://img209.imageshack.us/img209/9073/68740268th0.png"></img> </html>
Task 4
Now I don't know why malloc.h was there and was an Apple implementation, removing that allowed compilation using the unix command make.
The output was:
123 456 .78 -> 123 456 7.8 -> 123 456 78. -> Visited 5 states
The 3 states are shown here (shortest route), the other 2 states would be swapping the 4 and . and then possibly 1 and . or 5 and .