SE250:lab-X:dols008

Ok, first bit of fun is that the tar includes the wrong version of malloc.h. Deleting it as instructed fixes the problem in windows, but the proper solution would be including stdlib.h.

Task 1

I figured there were 9 places you could put the first piece. Having picked one of those places, 8 places remained where the second piece could be. So it goes on. 9*8*7*6*5*4*3*2 = 9! = 362880 (I didn't multiply by 1 because there's no 9th piece. Not that it makes any difference...)

I'm not sure how we're meant to estimate the number of edges. I suppose I can just work out the average number of moves from each state and multiply by the number of states. Actually, all I need to do is figure out how many states have the hole in the middle, multiply that by 4, and multiply the rest by 2. I guess there are about 8! states with the hole in the middle. So that's: 4*8!+2*(9!-8!)=806400

I hope I didn't just make a fool of myself.

Ok, I did make a fool of myself. Some states have 3 moves. So it should be: 4*1*8!+3*4*8!+2*4*8!=967680

Task 2

I suppose it's not permitted to make scathing comments about the single, lonely comment in search.c which we are supposed to read and understand.

It looks like breadth first search, but is probably smarter because it uses an ordered state list not a queue. I wasn't asked to look at any other files, so I was lazy and didn't check how it's ordered. So, a summary:

Add the initial state to the ordered state list and the visited set
While there are states in the ordered state list
   Pop a state off the list and look at it
   If the state is the goal state, stop searching
   Otherwise, go through the states children
      If the child is not in the visited set
         Add it to the visited set
         Add it to the ordered state list

Later on it says its depth first, so I suppose the ordered list acts as a stack. Fact remains that you can't tell from just search.c.

Task 3

It said by hand, so I did it by hand. Don't worry, I got it right. Had to change the dot command in graph.c of course.

Task 4

It will never go to a state it has been to before. It seems to have a priority associated with moving each direction. If it can move the empty square left, it will. Failing that it will move it down. I think up is next, followed by right. If it can't do anything (i.e. it's been to all the child states) it will skip to a previous state which it hasn't fully explored. Actually, I'm really not sure about the priorities for which state to visit, it's quite hard to tell.

Task 5

Once I actually had it solving the same problem my graph applied to, it solved it nice and quick. 2 moves, 5 states visited. See below as to why.

Task 6

So after reading through piles of code to find this 1 line change I found it actually IS best first. It's using the Manhattan distance to prioritize. I guess the 1 line change (not in search.c mind) is to break the closer_state function.