Check entries against their own indices, stopping on the first mismatch:The loop invariant is and for every . The loop variant is . A false guard means either every position has passed or the next position is wrong, so the returned Boolean is true exactly for the identity permutation. Neither the game nor its history is changed. Short-circuit evaluation protects the final indexed comparison.
def isIdentity: Boolean = {
var i = 0
while (i < game.length && game(i) == i) {
i += 1
}
i == game.length
}Allocate a distinct game and copy every destination entry from the corresponding source position:The loop invariant says that the receiver is unchanged and destination positions before
def flip(k: Int): Flip = {
require(1 < k && k <= game.length)
val result = new Flip(game.length)
var i = 0
while (i < game.length) {
val source = if (i < k) k - 1 - i else i
result.game(i) = game(source)
i += 1
}
result.flips = k :: flips
result
}i equal the reversal of the first source entries followed by the untouched suffix. The loop variant is . At exit the copying is complete. Reversal is a bijection on positions, so the destination remains a permutation. The returned object's array is independent of the receiver's array, while the immutable tail of its history list can safely be shared. The source's only supplied constructor randomizes the new array before the copy; that work is redundant but does not affect correctness. An additional private constructor could avoid it without changing the required result.The history is built by prepending, so reverse it when displaying chronological moves:Thus a reverse-stored history
override def toString: String =
game.mkString("[", ", ", "]") +
" history of flips: " + flips.reverse.toString[3,2,4] is displayed as List(4, 2, 3). The initial empty history remains List(). Neither traversal mutates the game or the immutable history. Displaying the stored list without reversing it would describe the moves backwards.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.
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 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.
Articles by others on the same topic
There are currently no matching articles.