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

[Ian Broster]

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