6 ms·
Here are the maximum number of steps required through 10, and likely maximum number of steps required through 12: 6: 14 7: 26 8: 74 9: 86 10: 126 11: 106
by rokicki 2y ago
Here are the maximum number of steps required through 10, and likely maximum number of steps required through 12:
6: 14
7: 26
8: 74
9: 86
10: 126
11: 106 (?) (full state space not explored)
12: 130 (?) (full state space not explored)
- rokicki 2y agoFinished with a full state-space search of 11; worst case is indeed 106 (vs 126 for 10).
- rokicki 2y agoFinished with a full-state search of 12; worst case is indeed 130. Found a game for n=14 that takes 172 moves: 6 11 8 2 7 10 9 12 4 1 14 3.
- 61u 2y agoJust wondering... How do you calculate the minimum number of steps fast enough?
- rokicki 2y agoTo solve a particular position, I just use level-by-level breadth-first search until a level contains two values that are reverses of each other. To explore the entire state space of possible initial positions, I use a number of tricks; I'll be writing that up pretty soon. I've explored through n=12 already, and expect to finish n=13 and n=14 pretty soon. I'm not sure if I'll be able to do n=15. And by the way, I've found a position for n=14 that requires 206 moves to solve.