mreid@ptc.com (michael reid) writes:

unfortunately, this estimate is too optimistic. the number of positions
within 10 face turns of start is more like 2.6 x 10^11.

An upper bound for number of positions reachable after 10
turns is

18 * 12**9

which is 92,876,046,336. Admittedly this number is closer to 2.6e11
than 1e10, but the number is an upper bound. It seems to me I
remember reading that the limiting branching factor (for q+h turns) is
about 9.5 and is reached rather quickly. The value of

18 * 12 * 12 * 12 * 9.5**6

is 22,864,298,166.0 (according to 'bc'), which should be within reach
of brute force algorithms. Unfortunately this approach requires
several hundred gigabytes of disk space but that could be spread out
over lots of physical machines (parallelizing could also result in
speeding up the computation). Anyone know where we could find 1000
machines with a few hundred megabytes free each?

Well, maybe not just yet. But soon.

regards,

Tim Rentsch