SE250:lab-X:mcar147

Back to Lab Reports

Lab X

Pre-lab

Down load stuff required. Done. Make the package... Well this might take a short while to figure out.

45 minutes into the lab we figure out why nothing is working. Someone *cough*John Hamer*cough* had been fiddling around with the files and had changed what search.c was solving.

Task 1

For the first space there are 9 possible numbers, 8,7,6,5,4,3,2,1 or " ". Next one has 8 possible, and so on down. Total possibilities, 9! 362880 total states...

Task 2

Summary of the searching algorithm... Right... Here I go

First it does some setting of some values, finds all the children of the current state into the stack, checks that state with the goal, then tosses it away and takes the next one from the stack.

Task 3

Yes... I drew this by hand...

            1 2 3
            4 5 6
            _ 7 8

    1 2 3             1 2 3
    _ 5 6             4 5 6
    4 7 8             7 _ 8

_ 2 3   1 2 3     1 2 3   1 2 3
1 5 6   5 _ 6     4 _ 6   4 5 6
4 7 8   4 7 8     7 5 8   7 8 _
(And back to the original... But that shouldn't happen)

Task 4

Depth first search goes all the way down one path before doubling back to the last known intersection and then going down that one. In this case it would go 5,3,2,4,7,6,8.

   5
  / \
 3   7
/ \ / \
2 4 6 8

If it was breadth first it would be 5,3,7,2,4,6,8

Task 5

Yep. It fits

Task 6

Can't figure out what to do here... And neither can anyone else as of yet

Task 7

Depth: 131356 states visited

Breadth:

Task 8

Breadth searching is good when you are close to the goal state, while Depth is better if you have really long way to go and thus need to take lots of steps. And with depth you can get lucks and hit the goal on the first time through to the deep.

Task 10

This task will take some time so even if I get to it I likely won't do it.