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

[Alan Burlison]

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