[r-t] Bobs only Erin Triples (was: Composition search)
Richard Smith
richard at ex-parrot.com
Wed Nov 25 10:20:02 UTC 2015
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
More information about the ringing-theory
mailing list