Dik.Winter@cwi.nl writes:

But it can take long. Getting a minimal solution if the length is 16
or less appears to be doable. If the length is 19 or more it takes an
awfully long time. What I have found until now is:
1. There are no configurations known that require 21 turns or more,
and I checked an awfully large number.
2. There are known configurations that require 18 turns.
The middle part is a grey area.

How hard would it be to write a program to try the following?

1) Initialize set S with a configuration that requires a large number
of turns (the max, perhaps).

2) Test the length of all configurations one turn from any
configuration in S.

3) If one or more of these has a minimum length longer than the
initial position, replace the set S with the set of those
configuration with longer length (of course print out useful
intermediate result).

4) If none of the test positions has a minimum length longer
than the length of positions in S, replace the set of test positions
with positions one more turn away, and test again until 3 works.
(Obviously it would be useful to store something about previous
results so that work is not redone needlessly. I think it's
easy to figure out what information should be stored, although
I haven't done so.)

5) Give up when patience is exhausted.

It would be nice to get a higher lower bound, and this seems
like a plausible way of doing so.

regards,

Tim Rentsch