Searches for all callings from rounds to a target row.
We search by exploring a tree structure where each node in the tree
represents a single Row. We work backwards from the target row hoping
to find rounds at the required number of steps.
Sixes (in Stedman) alternate between slow and quick and we can work around
this complexity by searching in steps of a "pair" of sixes, being a call, a
slow six, another call, and a quick six. Any row can be followed by any of
seven other rows.
The tree therefore expands rapidly. The node for the target row is connected
to seven other nodes; the next layer has 49 nodes and there's 343 after that.
By the time we get to 11 steps (22 sixes or a course of Stedman Cinques)
we would have 2,306,881,200 nodes in our tree. We need to optimise.
We can prune the tree as we go by using a data table that stores the minimum
number of steps needed to get from rounds to the target row. This can easily
be generated in advance and works as follows:
Say (for example) our target row can only be reached from rounds after a
minimum of 7 steps.
Iterate over the seven nodes connected to the target row (representing the
rows two sixes before the target row with each calling transposition).
For each node, check the minimum distance from rounds. If that is more
than 6 steps then discard the node (we're moving away from rounds).
Continue on from each remaining node.
Our list of transpositions already excludes undesirable callings (being -s
or ss). We also need to filter out touches where these callings develop
between pairs. We can do this as we go.
Searches for all callings from rounds to a target row.
We search by exploring a tree structure where each node in the tree represents a single Row. We work backwards from the target row hoping to find rounds at the required number of steps.
Sixes (in Stedman) alternate between slow and quick and we can work around this complexity by searching in steps of a "pair" of sixes, being a call, a slow six, another call, and a quick six. Any row can be followed by any of seven other rows.
The tree therefore expands rapidly. The node for the target row is connected to seven other nodes; the next layer has 49 nodes and there's 343 after that. By the time we get to 11 steps (22 sixes or a course of Stedman Cinques) we would have 2,306,881,200 nodes in our tree. We need to optimise.
We can prune the tree as we go by using a data table that stores the minimum number of steps needed to get from rounds to the target row. This can easily be generated in advance and works as follows:
Our list of transpositions already excludes undesirable callings (being
-sorss). We also need to filter out touches where these callings develop between pairs. We can do this as we go.