Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 3 / f / 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. 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.