[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