SE250:lab-X:mgha023

Number of states and edges of 8 piece puzzle

Well, since its a 3 by 3 puzzle, then I have a feeling the number of states could be 9!= 9x8x7x6x5x4x3x2x1 = 362880 states.

-->Well, if in each state, there are two legal moves possible, then in in total, there should be 362880x2 = 725760 edges.

• The above statement is wrong, but it's here so that I know it's wrong. Hmm, I was just told that it isn't as simple as that. That's because, all states don't have the empty space in the corner. The empty space could occur in the middle too. And that spells trouble as the number of moves possible increases to 4. If in the middle on the side, then the number of moves is three. So it's not that simple you see. Oh, what did I expect, has anything been simple in these labs?

Aha! Solved: Out of 9 states, 4 states will have the empty square in the corner, 4 states will haev empty square in the middle of the side, and 1 state will haev it , bang in the middle. So no wfor each corner state, there are 2 edges (2 likely moves), adn so for 4 corners, there is 4*2 = 8 edges. For the middle of the side states, there are 3 edges each so total are 4*3 = 12 EDGES. Finally, for the middle empty square state, there are 4 edges, so total is 1*4 = 4 edges. So, for a total of 9 states, there are 24 edges in total (8+12+4). Hence, for 362880 states, there are (362880 * 24) / 9 = 967680 edges.

yay:D

Summary of search algorithm

Uh, I need to read that again. Few minutes later : blink, blink Few more minutes later: blink, blink, blink, blink

Half an hour later: It says in the handout that the algorithm uses a "depth first" search stratey. So I gues it must be one then. Can't say too much about the code becuase I'm not sure I understood it completely.

ok so:

while something is not empty, pop that something, and next, if we are in the same state, then success and exit the code. 
If not, get hte children and iterate through them and add to the stateset and relase them.