Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 4 / e / Solution

Give each solving session a shared visited set keyed by immutable snapshots of permutation contents, for example game.toList, and insert the initial snapshot immediately. Have all successor objects refer to that same session's set. The refined flip first constructs the candidate state; if its key is present, return None. Otherwise add the key immediately and return Some(candidate). The search enqueues only Some results. Keys must compare contents rather than array identities, and a fresh solving session must start with a fresh visited set.

Marking at generation time prevents the same state from being queued repeatedly, including the immediate cycle made by applying the same reversal twice. First discovery in breadth-first search already has minimum depth, so discarding later discoveries cannot remove a shorter solution. The graph now has at most $n!$ admitted states. If only cycles along one path were to be rejected, a path-local set would suffice, but it would still repeat states reached by different paths; the shared session-wide set avoids both kinds of repetition. Public game fields must not be externally mutated while their states are being searched.