SE250:lab-X:sbas046
Task 1
Number of states: calculated by 9 factorial (9P9)
362880
Number of edges: the number of state transitions are 9!/2(going back to the same state) and the average number of legal moves from each state is 24/9. Hence the number of states edges are (9!*24)/18
483480
Task 2
- while the state is not empty:
- looks at the adjacent states. (pops off the ordered state list)
- if the state is the final state then break the program.
- else add the state to the ordered state list
- repeat
Task 3
<html><a><img src="http://img27.picoodle.com/img/img27/4/6/2/f_graphm_08036dd.jpg" border="0" alt="Graph" /></a></html>
Task 4
Here are the last few searches the program performs before finding the final state. It is depth first search. It looks at its children's children until it all the children are either empty or they have already been visited.
126 5.4 783 126 54. 783 126 543 78. 12. 546 783 126 584 7.3 126 584 73. .26 154 783 2.6 154 783 26. 154 783 264 15. 783 264 153 78. 264 153 7.8 142 6.5 738 142 65. 738 142 658 73. 142 658 7.3 142 .65 738 142 765 .38 142 765 3.8 142 765 38. $ 76. 385 142 7.6 385 1.2 746 385 12. 746 385 126 74. 385 126 745 38. 126 745 3.8 126 745 .38 126 .45 738 126 4.5 738 126 45. 738 12. 456 738 1.2 456 738 152 4.6 738 152 436 7.8 152 436 78. 152 43. 786 152 4.3 786 1.2 453 786 12. 453 786 123 45. 786
Task 5
The search.exe file lists the shortest path from the initial state to the final state whereas the graph details every state and edge.