[r-t] Bobs only Erin Triples (was: Composition search)
Richard Smith
richard at ex-parrot.com
Wed Nov 25 13:07:51 UTC 2015
Alan Burlison wrote:
> I was wondering if there was any benefit in doing a
> breadth-first search rather than depth-first and using the
> intermediate results to more aggressively prune the search
> tree but I'm not sure if that will help or not.
I've played with it a bit, but never made much headway.
The problem is that not many short touches run false so it
doesn't prune the search space sufficiently to affect the
tractability. Nevertheless, do try it. Perhaps you'll have
some new insight that's eluded me and the many others who
have attempted this.
It seems to me that if a bobs-only extent is ever found or
if it's proved impossible, it will require significant
progress in one of four areas:
1. "Magic blocks". This is how bobs-only Stedman was
cracked. It may be possible to identify some class of
subgraph with properties that would then make it highly
likely that an extent could be found without much further
effort. The problem then becomes one of searching for a
subgraph with the requisite properties. The subgraph may
simply be a short round block, or something more complex.
2. Theory. A major theoretical advance could have
significant consequences, particularly towards proving the
inverse if no extent exists. If anyone ever proves or
disproves the LovĂˇsz conjecture, that proof may provide such
an advance. I've long felt that the theory of Q-sets is a
special case of a more general theory of linkage. If so,
depending what that theory is, it might have major
implications to the subject of bobs-only Erin. It's worth
noting that the problem of finding Hamiltonian cycles on
Schreier coset graphs (or even Cayley graphs) has never been
proven NP-Hard. If it is, that limits what more general
theory might exist, but personally (and perhaps
controversially) I suspect it is not.
3. Algorithms. Most current work is devoted to searching
for n-part compositions as its tractable for certain n.
I've lost track of which structures have been eliminated so
far; Philip says I ruled out a 7 part, but my recollection
is hazy. Careful refinements to the algorithm might bring
the a smaller value of n in range, and that search might
prove fruitful. Pruning rotations is an obvious strategy
for one-part searches but is difficult in multi-part
searches. Factoring out Q-sets (when they exist) is another
possibility, but not easy to implement. Another possibility
is to prune the tree when a row becomes unreachable, but
that requires care to make sure the heuristics used actually
speed up the search. A carefully written search using many
of these strategies may be sufficient to target the next
multi-part structure.
4. Technology. Over time, Moore's Law will help bring
longer searches in range, but by itself it won't be
sufficient. There are 10^252 sequences of 840 plains and
bobs, and knocking a few zeros off that number makes no
material difference. But maybe it will contribute to making
the next multi-part search possible. A massively
distributed search of the sort done by SETI at home might
achieve something. But the most promising technological
advance would be quantum computing. This seems the sort of
problem that would be made vastly more accessible by a
sufficiently big quantum computer, but that may be 50 years
away.
RAS
More information about the ringing-theory
mailing list