Use breadth-first search with the supplied FIFO queue, taking one edge to mean one permitted prefix reversal:The FIFO queue holds pending paths in nondecreasing history length. Initially it holds only the zero-move path. Removing a path at depth and appending its children at depth preserves that order. The inner loop invariant says that precisely moves of the removed state have been appended; its loop variant is while the guard holds. The first identity state removed therefore has the minimum possible number of moves. A stack-based depth-first search does not generally have that property.
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)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 moves. Each search depth has finitely many paths, with at most 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.
Articles by others on the same topic
There are currently no matching articles.