SE250:lab-X:zyan057
Jump to navigation
Jump to search
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!