SE250:lab-X:zyan057

Task1

Calculate how many different states exist for the 8-piece puzzle.Estimate the number of edges in the complete state space graph. Explain how you made these calculations in your report.

• There are 9! different states.
• There are 9 possible pieces to fit in the first position, 8 pieces possible for the second position, and so on. i.e. 9*8*7*...*1 = 9!
• For each block at the corner: 2 possible moves
• at the side: 3 possible moves
• at the center: 4 possible moves
• Number of edges = (2*4+3*4+4*1)*9! = 24*9!