Many problems, such as the sliding-tile puzzles, gen-
erate search trees where different nodes have different
numbers of children, in this case depending on the po-
sition of the blank. We show how to calculate the
asymptotic branching factors of such problems, and
how to efficiently compute the exact numbers of nodes
at a given depth. This information is important for de-
termining the complexity of various search algorithms
on these problems. In addition to the sliding-tile puz-
zles, we also apply our technique to Rubik's Cube.
While our techniques are fairly straightforward, the
literature is full of incorrect branching factors for these
problems, and the errors in several incorrect methods
are fairly subtle.