SE250:lab-X:klod004

THE LAST LAB

I got the program running after a while, I had to bang my head with the dot command thing again as in lab 8. But my end result was a pdf file that had a diagram of the states and the moves of the puzzle.

Task 1

This task involves calculating the different states that exist for a 8-piece puzzle. The number of states are 9 factorial, which is: 362880. And the number of edges(complete number of legal moves) is a bit harder to calculate, but as I see, each state has a possibility of at least 2 moves, with the centre having the possibility of having 4 moves. So a good estimate would be 4!x2x9 + 4!x3x9 + 1x4x9 I came up with that estimate, which results to 432+648+32. I tried to think when the blank space is in the corners(4!x2x9), when the blank space is in the centre(1x4x9) or when it is the edges(4!x3x9).

Task 2

This task involves writing a summary for the search algorithm.

As far as I have read and understood, this algorithm uses a stack, pushes the states one by one into a stack, processes each state and looks at the next state, and determines if the state has been visited or not, and if the state is the final state that we want or not.

Task 3

Involves hand drawing the states, I could scan and upload, but can't really be bothered at this stage.

Task 4

The search algorithm, depth-first search, goes in one direction searching into the children and their children, and continues until it hits a dead end, then starts traveling backwards visiting the children it missed. This is the faster method of finding state, and doesn't eat up much space.

Task 5

This gives the states that were visited before we find the state we are looking for, and does not list all the states. And also, this actually looks like the puzzle as in the way it is printed on the screen, where we can actually see the movements.