[rokicki]

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)

[61u]

Just wondering... How do you calculate the minimum number of steps fast enough?

[rokicki]

To 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.

[rokicki]

Finished with a full state-space search of 11; worst case is indeed 106 (vs 126 for 10).

[rokicki]

Finished 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.