• Some statistic report about 88th puzzle

Question related to mission The 88th Puzzle

 

I have investigated the 88th puzzle.

1. size of all state

C(12,2)*C(10,2)*C(8,2)*C(6,2) = 1247400

2. all problems are solvable?

Yes.

This means we can always get solvable problem if we shuffle the goal.

3. the longest path

maximum length is 18.

14 states have maximum length.

  1. (3, 3, 1, 1, 0, 0, 2, 4, 0, 2, 4, 0) 111233434422131133 18
  2. (3, 1, 3, 0, 1, 0, 0, 4, 0, 2, 4, 2) 112344242343442311 18
  3. (0, 1, 3, 2, 0, 1, 4, 0, 3, 2, 4, 0) 111331244221124224 18
  4. (3, 1, 3, 0, 0, 1, 0, 4, 0, 2, 4, 2) 113342221114242243 18
  5. (0, 1, 3, 0, 1, 0, 0, 4, 3, 2, 4, 2) 111244242334344211 18
  6. (0, 1, 3, 0, 1, 3, 0, 0, 4, 4, 2, 2) 142422443311312334 18
  7. (3, 1, 3, 2, 1, 0, 0, 4, 0, 2, 4, 0) 111334344221211333 18
  8. (3, 1, 3, 4, 1, 0, 0, 4, 0, 2, 0, 2) 113342212142422143 18
  9. (3, 1, 3, 0, 1, 2, 0, 4, 0, 0, 4, 2) 111223121123344224 18
  10. (3, 0, 3, 0, 1, 0, 0, 4, 1, 2, 4, 2) 112344242343442131 18
  11. (3, 2, 3, 0, 1, 0, 2, 0, 4, 1, 4, 0) 142211243344234421 18
  12. (3, 1, 3, 0, 1, 0, 4, 0, 0, 2, 4, 2) 111223121133442422 18
  13. (0, 1, 4, 1, 0, 3, 0, 4, 0, 2, 3, 2) 111222343443311122 18
  14. (3, 1, 0, 0, 1, 0, 3, 4, 0, 2, 4, 2) 113342212114242234 18

4. path length distribution (length : count)

  • 0: 1 ... GOAL
  • 1: 4
  • 2: 14
  • 3: 48
  • 4: 152
  • 5: 476
  • 6: 1438
  • 7: 4123
  • 8: 11153
  • 9: 28189
  • 10: 65173
  • 11: 132986
  • 12: 226383 ... average = 12.849
  • 13: 301114 ... mode = 13, median = 13
  • 14: 283209
  • 15: 155439
  • 16: 35627
  • 17: 1857
  • 18: 14 ... maximum = 18

5. variation of 88th puzzle

If we can rotate both direction, the puzzle become more easy to solve. The path length distribution is follows.

  • 0: 1 ... GOAL
  • 1: 8
  • 2: 40
  • 3: 192
  • 4: 906
  • 5: 3940
  • 6: 15634
  • 7: 54486
  • 8: 155462
  • 9: 326708 ... average = 9.519
  • 10: 423672 ... mode = 10, median = 10
  • 11: 241978
  • 12: 24323
  • 13: 50 ... maximum = 13

Thanks