Body: <p>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 <span class="math-container">$\frac{9!}{2}$</span>. However, I think it should be <span class="math-container">$9!$</span>. 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 <span class="math-container">$2$</span>. So why do we divide the total number of (initial) states by <span class="math-container">$2$</span>? What extra states are we counting?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-30T11:43:08.410Z
Comments.Text: 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"
Comments.UserDisplayName: Criticize SE actions means ban
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-30T12:20:13.013Z
Comments.Text: @user253751 Just one thing: What does that llRC mean?
Comments.UserDisplayName: Emad
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-30T12:51:40.680Z
Comments.Text: "If I remember correctly"
Comments.UserDisplayName: Criticize SE actions means ban
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-30T13:49:50.797Z
Comments.Text: @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!```
Comments.UserDisplayName: Omar AlSuwaidi
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-30T15:30:55.420Z
Comments.Text: @OmarAlSuwaidi But only half of them are reachable
Comments.UserDisplayName: Criticize SE actions means ban
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-30T15:38:54.980Z
Comments.Text: @user253751 ahhh I see, thanks for the clarification, it makes sense now
Comments.UserDisplayName: Omar AlSuwaidi
Tags: <8-puzzle-problem>
Title: Total number of states reachable from the initial state in 8-puzzle problem
UserDisplayName: Emad
ThreadText: # Total number of states reachable from the initial state in 8-puzzle problem
  
  (Asked by: username_0 on 2021-08-30)
  
  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?
  
  **Tags:** 8-puzzle-problem
  
  > **Comments:**
  > **username_1**: 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"  
  > **username_0**: @user253751 Just one thing: What does that llRC mean?  
  > **username_1**: "If I remember correctly"  
  > **username_2**: @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!```  
  > **username_1**: @username_2 But only half of them are reachable  
  > **username_2**: @user253751 ahhh I see, thanks for the clarification, it makes sense now  
  
  ---
  
  ## 0 answers
  
  