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

Ian Broster ian at broster.co.uk
Wed Nov 25 12:12:36 UTC 2015

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

You can remove rotations of the same touch from the search space by using
the path from the root to the current node as your starting point for the
next recursion.

For example, if your path from root to node is ppppppb (because you have
already found that ppppppp is false (or actually, comes round and makes
any longer touch containing it false - awkward corner case!) then you do
not need to try (ever) the sequence ppppppp in your search space. You do
this by using the path ppppppb to prune direct the next recursive call.

Sorry that's not explained very well! It was years ago I last coded
something like that.

As you get further through the search space, the gains from this get much
greater. i.e. if your path starts pbbb... then you never need to look at
anything with more than one consecutive p.

Obviously, an easy optimization is to do this in a loop rather than a
recursive call. That more than doubles the speed, but that optimization is
clearly secondary to reducing the search space!

Ian

--
Ian Broster

```