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

Alan Burlison alan.burlison at gmail.com
Tue Nov 24 20:10:32 UTC 2015

On 24/11/2015 18:30, Don Morrison wrote:

> There may well be something useful here, but I don't think it's going to be
> as easy as this example seems to imply. You rarely run into falseness
> locally, it's in more distant places in your path through the graph that it
> becomes an issue. For example, ANY three, or even four, division sequence
> in Erin is guaranteed to be true, and only one of the thirty-two five
> division sequences is false. Things probably don't get interesting until
> you're up at thirty or forty division sequences, and caching the billions
> of them that there are is not going to be practical (and I doubt there's
> any useful scheme for flushing most while retaining the most useful; LRU,
> for example, probably doesn't help much).

I'm assuming that the 'distance' between divisions in a sequence isn't
relevant when it comes to establishing falseness, if division 324 and
division 9195 are false relative to each other, then it doesn't matter
if they are next to each other in a sequence or 5000 steps apart, the
result is still false.

If that's true then when looking for the next division to add to a
sequence, I'm assuming the set of candidates can be constrained as follows:

1. The candidate divisions must not already be in the sequence.

2. The candidate divisions must start with the same row that the current
sequence ends with (or is it one change away? as I said earlier, I'm not
sure which is correct).

3. The candidate divisions must not be false relative to any of the
divisions in the set.

I'm assuming that the set of all possible Erin plain and bob 6-change
divisions is 7! * 2, i.e. 10080, is that correct? If that's the case
then there are around 51 million 2-division pairs that would potentially
need comparing to each other to establish any falseness, unless I'm
missing something. That seems doable.

With graph search problems, if you do the maths on the size of the
potential search space it often looks like they are computationally
infeasible. The best way of attacking them is to consider if there are
any predicates that enable you to immediately discard entire subtrees.

The other approach is to use cost functions in conjunction with search
algorithms such as A* to direct the search, but I'm not sure if that
would be possible in this

> Note that in saying this I'm assuming a one part; if you've modded
> out by a part head things might get more interesting earlier.

I'm not sure what you mean by this, sorry.

--
Alan Burlison
--