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

[Alan Burlison]

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