Total number of states reachable from the initial state in 8-puzzle problem

Asked Aug 30 '21 at 09:00

Active Aug 30 '21 at 09:00

Viewed 567 times

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 Aug 30 '21 at 09:00

Emad

2

IIRC, 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" – Stack Exchange Broke The Law 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" – Stack Exchange Broke The Law 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 – Stack Exchange Broke The Law 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

Total number of states reachable from the initial state in 8-puzzle problem

0 Answers0