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

Alan Burlison alan.burlison at gmail.com
Wed Nov 25 11:25:31 UTC 2015

On 25/11/2015 10:20, Richard Smith wrote:

> 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.

I suspected it almost certainly wasn't a practical approach, thanks for 
the confirmation ;-)

> 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.

Thanks for that concise explanation, that makes sense. I'd not figured 
out the limit of 2 that it could be false against, interesting. Thanks 
also for the pointer to the part of RCL that does this already, I'll go 
study it.

> 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;
>      }
>    }

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. Thanks for all the food for thought!

Alan Burlison

More information about the ringing-theory mailing list