Number of possible state 15 puzzle russell norving error?

468 Views Asked by At

I'm reading Artificial Intelligence(3th edition) Russell Norvig. In a chapter the authors declare that the number of possible combinations in 15 puzzle is 1,3 trillion (15!) but I am not convinced. The possible combinations for me is 16!, around 20 trillion. It's possible that this important book it's wrong?

Note: I am not considering the number of states that can be reached!

1

There are 1 best solutions below

1
On BEST ANSWER

It is always possible that books are wrong, even important ones. One of my Differential Equations professors had a habit of assigning problems from the book which were impossible to solve -- asking us to figure out why they were impossible, what the author might have intended instead, and what the solution to such a hypothetical question might look like.

To answer the rest of your question, we need to know what Norvig defined a "combination" to be. One plausible interpretation would have the $15$ tiles arranged in the $15$ squares which are not the bottom-right corner, and this can be done in $15!$ ways (exactly half of which are reachable in actual play). If you allow the blank square to be anywhere, yes $16!$ seems to be the correct count.