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

[Richard Smith]

Alan Burlison wrote:

> I've looked at the code in the C++ ringing library, it appears to check for 
> falseness by comparing each row to all the rest that follow it within a 
> division. That can be improved on by caching the rows within each division in 
> sorted order rather than ringing order and then doing a merge sort or binary 
> search when comparing against other blocks.

There is code in the C++ Ringing Class Library that treats 
falseness like that, and it has its uses.  But if you find 
youself using it in a big search, you've already lost.  The 
table_search class is closer to what you want.

For Erin, there are 2520 possible sixes, or six heads if you 
prefer to think of them like that.  Each six (head), h, is 
false against two others, h.f1 and h.f2, and each six has 
two possible successors, h.p and h.b.  You want to start by 
precomputing the 2520 x 4 multiplication table; thereafter 
you denote sixes by reference to a row of this 
multiplication table.  The Ringing Class Library has the 
multtab class to do this, and optimised multtab::row_t which 
is wrapped row numbers into the multiplication table.

As you do the search, you store a table of the 2520 possible 
sixes and mark them as used if they're included or if 
they're precluded by falseness.  The inner loop to do this 
is really simple:

   void recurse(size_t l, row_t h) {
     if ( l == 840 ) found();
     else if ( !rows[h] && !rows[h*f1] && !rows[h*f2] ) {
       rows[h] = rows[h*f1] = rows[h*f2] = true;
       recurse(l+1, h*p); recurse(l+1, h*b);
       rows[h] = rows[h*f1] = rows[h*f2] = false;
     }
   }

RAS