We can express the backtracking search as a recursive procedure ExtendRight: ExtendRight (PartialWord, node N in dawg, square) = if square is vacant then If N is a terminal node then LegalMove (PartialWord) for each edge E out of N if the letter l labeling edge E is in our rack and l is in the cross-check set of square then remove a tile l from the rack let N' be the node reached by following edge E let next-square be the square to the right of square ExtendRight (PartialWord .
Because there are only 26 letters in the alphabet, we can conveniently store each cross-check set as a bit-vector in one 32-bit machine word, and do membership testing quickly.
It is useful to put fictitious squares with empty cross-check sets at the end of each row to serve as sentinels, preventing us from trying to extend words off the board.
We conveniently compute these cross-sums while computing the cross-check sets.
Through the abstractions of anchor squares and cross-check sets, we reduce a two-dimensional problem into one-dimension.
We could move the anchor-square cross-check pruning to the beginning of left-part generation (where it will prune larger subtrees) by first making a list of all possible left-parts and arranging them by last letter and length.
To do this efficiently, it would be helpful to first make a list of anchor descriptors, keeping for each one the maximum left-part length and the anchor cross-check set.