[r-t] Crambo

[Richard Smith]

Philip Earis wrote:

> RAS:
> "What additional criteria did he have?  No more than two consecutive
> blows in one place?  No single changes?"
>
> Is an exhaustive search with these criteria feasible?

Not with the code I have to hand, and I suspect not at all,
though I'd need to look further to be sure.

> How about also constraining it by requiring as much
> symmetry as you can get?

Glide symmetry can easily be used to optimise the search as
it doesn't pick out any row to be special (i.e. it has no
pivot row).  This means that I can look for a true half-lead
and then double it up.

Handling the other symmetries in an n-part composition are
less easy.  When looking efficiently for an n-part
composition, it is usual to factor out the n-part-ness right
at the beginning.  This is done by arbitrarily choosing a
part end group and relying on the fact that any n-part
extent can be such that it has any (conjugate) n-part lead
end.  You can then search for 1-part extent over a graph
of size N!/n (mathematically: the Schreier graph of right
cosets of the part end group).  This speeds up the search
because you rule out inter-lead falseness at a much earlier
stage.

By requiring palindromic and/or rotational symmetry, you can
only do one of fixing the symmetry point and/or fixing the
part end group.  If you don't fix the symmetry point, it
makes it hard to use the symmetry to speed up the search,
and if you don't fix the part-end group, it makes it hard to
locate inter-lead falseness when it arises.  (In both
cases, it *is* possible -- it's just that the algorithm is
that much more complicated and error-prone.)

>  Or by not allowing adjacent
> places in the notation?

So just x,14,16,36?  That's a good idea.  That
*significantly* reduces the search space.   I'll look into
that.

RAS