= Solution
Use <breadth-first search> with the supplied <FIFO queue>, taking one edge to mean one permitted <prefix reversal>:
``
def solve(puzzle: Flip): Flip = {
val pending = scala.collection.mutable.Queue[Flip]()
pending.enqueue(puzzle)
while (!pending.isEmpty) {
val current = pending.dequeue()
if (current.isIdentity) return current
var k = 2L
while (k <= current.game.length.toLong) {
pending.enqueue(current.flip(k.toInt))
k += 1L
}
}
throw new IllegalStateException("No solution")
}
val puzzle = new Flip(n)
println("Solving:")
println(puzzle)
val answer = solve(puzzle)
println("Solved:")
println(answer)
``
The <FIFO queue> holds pending paths in nondecreasing history length. Initially it holds only the zero-move path. Removing a path at depth $d$ and appending its children at depth $d+1$ preserves that order. The inner <loop invariant> says that precisely moves $2,\ldots,k-1$ of the removed state have been appended; its <loop variant> is $n-k+1$ while the guard holds. The first identity state removed therefore has \b[the minimum possible number of moves]. A <stack>-based <depth-first search> does not generally have that property.
Termination does not rely on avoiding repeats in this first version. Every <permutation> can be sorted by <prefix reversal sorting>: place the largest misplaced value at the front if necessary, flip it into its final position, and repeat on the shorter prefix. This constructs a route of at most $2(n-1)$ moves. Each search depth has finitely many paths, with at most $n-1$ children per path, so <breadth-first search> reaches some solution depth after finitely many expansions. This gives a finite bound on remaining expansions before the first solution even though the repeated-state path tree is infinite. The one-element game is already solved. Repeated paths can nevertheless make time and storage enormous; part (e) removes that waste.
Back to article page
