I know it's a simple question but the book Artificial Intelligence by Russel says that the number of reachable states from any initial state in the 8-puzzle problem is $\frac{9!}{2}$. However, I think it should be $9!$. Note that we can't say if we rotate the grid horizontally then state we get is the same so as to divide the total number of states by $2$. So why do we divide the total number of (initial) states by $2$? What extra states are we counting?
Asked
Active
Viewed 301 times
2
-
2IIRC, swapping any two puzzle pieces in any state results in a state which is not reachable from the initial state. There is some kind of "parity" – user253751 Aug 30 '21 at 11:43
-
@user253751 Just one thing: What does that llRC mean? – Emad Aug 30 '21 at 12:20
-
"If I remember correctly" – user253751 Aug 30 '21 at 12:51
-
@user253751 Could you elaborate on that please? In permutations, we can also think of swapping any two states, resulting in a different state, yet the number of unique possible states is still ```n!``` – Omar AlSuwaidi Aug 30 '21 at 13:49
-
@OmarAlSuwaidi But only half of them are reachable – user253751 Aug 30 '21 at 15:30
-
@user253751 ahhh I see, thanks for the clarification, it makes sense now – Omar AlSuwaidi Aug 30 '21 at 15:38