SE250:lab-X:asin185

Lab x

Intro

In this lab we had to experiment with state-space search and uninformed search strategies. Just like the last lab i had to spend a good 20 minutes just looking at the code before begining. It seems like a fun lab.

Task 1

There are 362880 states exist for the 8-piece puzzle and one extra for the empty space used to move around the others, this is given by 9! as there are 9 sides al togather.The estimated number of edges i figured out with the following. This is because corners have 2 points then sides have 3 points and the middle has 4 points so therefore we have

(8!)*4 + (8!*4)*3 + (8!*4)*2 = 483840

Task 2

The main search algorithm for search.c is in my veiw stack. It "pushes" each state onto the stack and checks if this is the final state. If not it "pops" it and checks the next state.

Task 3

Will scan it and put up the scanning as soon as i can.

Task 4

The searh goes dept first into the left side and all its children and then back tracks back up.

.12
345
678
 ->
1.2
345
678
 ->
142
3.5
678
 ->
142
.35
678
 ->
142
635
.78
 ->
142
635
7.8

Task 5

Running the search code, It dont notice much :P. This solution compared with the solution in your state graph , the only aparent thing is that It goes through 2 moves and five states. This i think gives all the states visted. It gives all the states even if before we find the node we look for.

Task 6

At first i had no clue at all. After realizing the lab time is nearly over i got some help and figured out that we want to go through one side's depth for that branch adn then going to the next branch.

Task 7

We had to searche from the initial state to the goal state both breadth first and depth first search. Note how many states we go throuhg before we actualluy find our goal state.