I have access to less computing resources than I used to have.
As a result, I have been thinking about ways to conduct large
searches with less memory. There are no results here, just
some thoughts.

I will assume a quarter turn metric. It would be easy to
generalize the proposals below to other metrics, but I will
not do so.

We let C[n] be the set of all positions of length n. C[0] is
just {Start}, and C[1] is just Q, the set of twelve quarter
turns. We let T[n] be the union of C[k] for k in 0..n.

We assume that any computerized breadth first search for God's
Algorithm would build (in turn) C[0], C[1], etc., and would
store each C[k] in memory in some reasonable indexed and
searchable data structure. The details of the data structure
do not (I think) matter for the purposes of this note.

We assume that the primary constraint on the search is memory
size rather than time. These days, most anybody has access to
a machine (or machines) where a problem can be allowed to run
for hundreds or thousands of hours if necessary. A 486 or
Pentium on your desk would serve nicely, and a UNIX work
station would be even better. I have used both a 486 (running
OS/2 for multitasking) and a UNIX work station in this manner.
The machines could be used for other things while the cube
problems were running.

We assume that n is the largest n for which we can store C[n].
We assume that if we can store C[n], we can also store T[n].
For all practical purposes, T[n] and C[n] are about the same
size close to Start because C[n] is a little more than nine
times larger than C[n-1].

With this structure in hand, we could form all products XY for
X and Y in T[n]. We would simply form the products; we would
not try to store them. But having done so, we would have created
all positions in T[2n]. In some ways, this is not very useful.
That is, in general we would not know the length of any
particular XY, nor would we know the size of C[k] for k in
n+1..2n.

But as we formed the products, we could check them against any
position of interest, or against a small set of positions of
interest. We could then determine if any of the interesting
positions were in T[2n], and thus bound their length. (We
assume that none of the interesting positions are in T[n].
Otherwise, we could determine their length directly and none
of these Draconian measures would be necessary.) Such a
half-depth search has been discussed quite a few times before in
Cube-Lovers.

But here follows what I think is a new idea. What if we
formed all products XY for X in C[n] and Y in C[1]. Since
C[1] is Q, this is really just the procedure for a standard
depth first search. But we can't store C[n+1]. Can we
determine the size of C[n+1] anyway?

Try the following. The length of each XY is either n-1 or
n+1. Verify which case we have by reference to C[n-1], and
throw away the products of length n-1. But if the length of
XY is n+1, do we count it, or do we not?

The problem is that we might have XY=VW for X and V in C[n], Y
and W in C[1], X not equal V, and Y not equal W. Which do we
count and which do we not? Actually, there may be up to
twelve such products, so we need a way uniquely to determine
which product to count and which not to count.

Suppose we have XY in hand and wish to know whether to count
it. Form all products (XY)Z for Z in C[1]. There are twelve
such products, and at least one of them will be in C[n]. We
assume that C[1] can be ordered (probably already is) by our
data structure. Hence, we count XY only if Y'=Z*, where Z* is
the first Z such that XY(Z) is in C[n]. (Strictly speaking,
we would not have to form all products XY(Z). We would stop
once we found the first Z such that (XY)Z was in C[n]. We
would then either have Y'=Z*, or we wouldn't. But this only
reduces the number of products down from twelve to an average
of six.)

It seems to me that this procedure would work in principle,
but I am not sure how practical it would be. The problem is
that there would be a lot of products XY(Z) to calculate and
test. Is there any shorter method to determine whether or not
to count XY?

I normally write my sets C[k] out to a file. Any analysis I
wish to do is then run against the file after the fact. With
the new procedure I am describing, any analysis of C[n+1]
would have to be done as the products were being formed.

We can use a similar procedure to determine the size of
C[n+2], C[n+3], etc. up through C[2n], but things get more
complicated and more impractical.

For C[n+2], form all XY for X in C[n] and Y in C[2]. All such
products are in C[n-2], C[n], or C[n+2]. As before, we look
up XY in C[n-2] and in C[n], and throw it away if it is
already there. We then form all XY(Z) for Z in C[2] (there
will be 114 such products), and count the product only if
Y'=Z*, where Z* is the first Z in C[2] such that XY(Z) is in
C[n]. But this case is even more time consuming than the
C[n+1] case because we will on the average have to look at 57
products (57=114/2).

As an aside, I have considered creating C[n+1] as the
product of XY with X in C[n-1] and Y in C[2], rather than
as the product of XY with X in C[n] and Y in C[1], even
before running out of memory to store the results. We
still have to check for positions whose length is less
than n+1, and we still have to check for duplicate
positions of length n+1. But using C[n-1] and C[2]
would automatically eliminate from the search duplicate
positions such as ZRR'=Z or ZRL=ZLR. Or better still,
perhaps to create C[n+1] we should take X from C[n/2] and
Y from C[(n/2)+1]? Has anybody tried anything like that?

C[n+3] gets worse still. If we form all XY for X in C[n] and
Y in C[3], the length of XY may be n-3, n-1, n+1, or n+3. We
dispose of the n-3 and n-1 cases as before, but then we would
have to have a way to distinguish between the n+1 and n+3
cases. I think the procedure becomes truly impractical at
this point.

Anyway, that's it. Has anybody ever tried anything along the
lines I have outlined for a problem too big to store? If so,
did it work?

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                jbryan@pstcc.cc.tn.us
Pellissippi State                            (423) 539-7127
10915 Hardin Valley Road                     (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990