[r-t] Bobs only Erin Triples (was: Composition search)

[Richard Smith]

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