= Solution
Different move orders can lead to the same position, and the two occupancy <lists> also retain irrelevant insertion order. Thus this <search tree> repeatedly solves the same remaining game. For example, swapping the order of two `O` moves while leaving the intervening `X` moves legal can reach the same occupied <sets>.
Canonicalize each state by sorted occupancy <sets>, or by two <bitboards>, and apply <memoization> or a visited-state <set>. Expand each canonical position once, stopping at terminal states, and collect terminal positions in a <set>. There are at most $3^9$ cell assignments, many of which are illegal; this is much smaller than a <tree> of move permutations. \b[Store positions, not histories, when the requested output is distinct final positions.] Board rotations and reflections can reduce work further if handled as an additional equivalence: if the output must retain every oriented board, reconstruct those distinct orientations rather than silently returning one representative per symmetry class.
Back to article page
