arXiv:1705.04665v1 [] 12 May 2017

A Formal Characterization of the Local Search Topology
of the Gap Heuristic
Danniel Sihui Yang
Department of Computer Science
University of Toronto
Toronto, Ontario, Canada
dannielyang1996@gmail.com

Richard Valenzano
Department of Computer Science
University of Toronto
Toronto, Ontario, Canada
rvalenzano@cs.toronto.edu

Abstract
The pancake puzzle is a classic optimization problem that has become a standard benchmark for heuristic search
algorithms. In this paper, we provide full proofs regarding the local search topology of the gap heuristic for the
pancake puzzle. First, we show that in any non-goal state in which there is no move that will decrease the number of
gaps, there is a move that will keep the number of gaps constant. We then classify any state in which the number of
gaps cannot be decreased in a single action into two groups: those requiring 2 actions to decrease the number of gaps,
and those which require 3 actions to decrease the number of gaps.

1 Background
In this section, we provide background on the pancake problem and define the notation used in the rest of the paper.

1.1 Sequences and Permutations
In this paper, we represent a sequence σ of k elements from some set as σ = he1 , ..., ek i, where σ[i] then refers to the
i-th element of σ (i.e. σ[i] = ei )1 . If σ ′ = hg1 , ..., gk′ i, we use σ ◦ σ ′ to denote the concatenation of these sequences:
he1 , ..., ek , g1 , ..., gk′ i. A permutation π of size N is a sequence of the natural numbers from 1 to N , such that each
element in the sequence is unique.

1.2 The Pancake Puzzle Problem
An N -pancake puzzle state is a stack of N different sized pancakes. We represent this stack with a permutation of
size N , where entry i refers to the i-th smallest pancake and the order of the numbers in the permutation corresponds
to the order of the pancakes in the stack from top to bottom. For example, h2, 1, 4, 3i represents a 4-pancake stack in
which the second smallest pancake is at the top of the stack.
In any N -pancake state, there are N − 1 applicable actions or moves, denoted by M2 , M3 , ..., MN . Action Mk ,
called a k-flip, reverses the order of the first k values in the stack. Where Mk (π) denotes the permutation that is the
result of applying action Mk to π, this means that Mk (π)[1] = π[k], Mk (π)[2] = π[k − 1], and so on. For example,
M3 (h2, 1, 4, 3i) = h4, 1, 2, 3i.
Definition 1. Given N -pancake state πinit , the N -pancake puzzle task is to find the shortest or optimal sequence of
flips that transforms πinit into state πgoal = h1, 2, ..., N i.
1 As

is convention in the pancake puzzle literature, the first element of the permutation is at location 1.

1

1.3 The Gap Heuristic
A heuristic function h is a function from the set of states to the set of non-negative real numbers, where h(π) is
referred to as the heuristic value of π. A heuristic h is said to be admissible if for every state π, h(π) ≤ h∗ (π).
The gap heuristic (Helmert 2010), which we denote by hG , is most easily formally defined using the extended
permutation π e of π. π e is defined as π ◦ hN + 1i. The value N + 1 can be thought of as the plate below the pancake
stack, though we often refer to it as the N + 1-st pancake. Moreover, due to the one-to-one correspondence between π
and π e we often refer to π[N + 1], the “N + 1-st pancake” of π, or “location N + 1” in π.
For any j where 1 ≤ j ≤ N , an adjacency is said to occur in π e between locations j and j + 1, or between
pancakes π e [j] and π e [j + 1], if |π e [j] − π e [j + 1]| = 1. A gap is said to occur between those locations (or those
pancakes) if an adjacency does not occur. hG (π), is then given by the count of the number of gaps in π e :
hG (π) = |{j | 1 ≤ j ≤ N, |π e [j] − π e [j + 1]| > 1}|
Since any action can only add or remove at most one gap and there are no gaps in πgoal , hG is admissible.
If action Mi removes a gap when applied to state π (i.e. hG (Mi (π)) = hG (π) − 1), then Mi is called a gap
decreasing move in π. Similarly, Mi is a gap increasing move if it introduces a gap, while if it replaces one gap with
another or one adjacency with another, Mi is a gap neutral move.
We observe that there are always at most two gap decreasing moves in any state. This is because Mi can only
resolve a gap (if one exists) between locations i and i + 1, if π[1] is adjacent to π[i + 1] in πgoal , and this is only true if
π[i + 1] = π[1] + 1 or π[i + 1] = π[1] − 1. However, in many states there are no gap decreasing moves. These states
are said to be locked.

2 Locked States and Gap Neutral Moves
In this section, we formally prove that there is a gap neutral move in every non-goal locked state. We begin by showing
that there is at least one gap in any non-goal state.
Lemma 2.1. π is a goal state if and only if hG (π) = 0.
Proof. The fact that if π is a goal state, then hG (π) = 0 is obvious. As such, let us assume that hG (π) = 0 Then there
is no gap between locations N and N + 1 of π, which ensures that π[N ] = N . Similarly, there is no gap between
locations N − 1 and N of π, which ensures that π[N − 1] = N − 1. This argument can be extended to show that for
any 1 ≤ i ≤ N , π[i] = i. As such, π is the goal state.
We will now use this lemma to show that there is always a gap neutral move in any non-goal locked state.
Theorem 2.2. If π is a locked state that is not the goal, then there is a gap neutral move in π.
Proof. Let π be a locked state that is not the goal. First, we note that π[1] 6= N . This is because if π[N ] = N ,
then π[N ] 6= N , and so there is a gap between locations N and N + 1. Thus, MN is a gap decreasing move which
contradicts the assumption that π is locked. There are now two cases to consider.
Case 1: π[1] > 1.
Since π[1] > 1, π[1] < N since otherwise π is not locked by the argument above. As such, let e and e′ be the two
pancakes that should be beside π[1] in the goal state (i.e. |π[1] − e| = |π[1] − e′ | = 1). If π[ℓ] = e and π[ℓ′ ] = e′ , we
can assume that ℓ > ℓ′ without loss of generality. Since 1 < ℓ′ < ℓ, ℓ > 2.
Now because π is locked, there is an adjacency between locations ℓ − 1 and ℓ. Since ℓ > 2, Mℓ−1 is a valid action.
Moreover, Mℓ−1 will move π[1] on top of e, thereby replacing one adjacency with another. As such, Mℓ−1 is a gap
neutral move, thus guaranteeing that one such gap neutral move exists in π in this case.
Case 2: π[1] = 1.
There are now two subcases to consider. First, π[2] 6= 2. This means that π[ℓ] = 2 for some ℓ > 2 and so Mℓ−1 is
a valid action. This action will simply replace one adjacency with another by the same argument as in Case 1, and so
the statement holds in this case.
2

Now suppose that π[2] = 2. Since π is not a goal state, there must exist a gap between some two locations ℓ and
ℓ + 1 by Theorem 2.1. Because there π[1] = 1 and π[2] = 2, there is no gap between locations 1 and 2 in π, and so
ℓ ≥ 2. Thus, Mℓ is a valid move. Since π[2] = 2, this means that π[ℓ + 1] 6= 2 and so Mℓ (π) will also have a gap
between locations ℓ and ℓ + 1. Thus, Mℓ is a gap neutral move in π which replaces one gap with another. As such,
there is a gap neutral move in π in this case.
Having handled all cases, the statement holds.

3 Topology of the Gap Heuristic
In this section, we extend the work of Fischer and Ginzinger (2005) and provide a classification of states according
to the size of the plateaus around them. To simplify this analysis, we assume that in all states, there is gap between
locations N and N + 1. Doing so removes the postfix of a state if it is already sorted, since this portion of the state
will have no impact on the number of gaps or the optimal solution cost. For example, where π = h2, 1, 4, 3i and
π ′ = h2, 1, 4, 3, 5, 6, 7i, clearly hG (π) = hG (π ′ ) and h∗ (π) = h∗ (π ′ ).
We begin with some additional notation. Following Hoffmann (2005), a plateau for h is a connected set of one or
more states that all have the same heuristic value. An exit from a plateau with heuristic value ℓ is a state π such that
h(π) = ℓ and there is some neighbour π ′ of π such that h(π ′ ) < h(π). The exit distance of h from a state π is the
minimum number of actions needed to reach an exit. Note that this means than any exit has an exit distance of 0.
We also say that consecutive locations i, i + 1, ..., i + j in a permutation π is a strip of size j + 1 if there are no
gaps between the pancakes in those locations, and that sequence of locations is maximal (i.e. on either side of the strip
there is a gap or the end of the permutation). A strip of size 2 or more is descending if π[i] > π[i + 1] > ... > π[i + j],
and ascending otherwise. Two strips from i to i + j and i′ to i′ + j ′ where i ≤ i + j < i′ ≤ i′ + j ′ are in order if
the pancakes in the strip from i to j are smaller than the pancakes in the strip from i′ to j ′ . The first strip is the one
starting at location 1, and the rightmost strip is the one ending at location N . Where ℓ is the size of the first strip of a
state π that has at least two strips, the second strip starts at location ℓ + 1. The remaining strips are named similarly.
For example, h1, 2, 3, 5, 4i has two strips: the first strip is an ascending strip of size 3 from locations 1 to 3, and a
descending strip of size 2 from location 4 to 5. The latter strip is the second or rightmost one, and the two strips are in
order.
We now define the following family of states:
Definition 2. π is a Fischer-Ginzinger (FG) state if and only if π has at least two strips, and all strips in π are
descending, have a size of at least two, and are in order.
For example, h3, 2, 1, 5, 4i is an FG state, while h1, 2, 4, 3i and h2, 1, 3, 5, 4i are not FG states since they have an
ascending strip and strip of size 1, respectively.
We can now characterize states according to their exit distance. First, we notice that any state in which there is
a gap decreasing move has an exit distance of 0 by definition. For locked states, consider the following corollary of
Lemma 5 from Fischer and Ginzinger (2005):
Corollary 3.1. The exit distance of hG for any locked state that is not an FG state is 1.
Fischer and Ginzinger proved this by providing appropriate sequences of actions that could decrease the number
of gaps for all possible cases of non-FG locked states. Fischer and Ginzinger also provided a method for sorting any
FG state π using at most 2 · hG (π) actions. This method always decreases the number of gaps in π in 3 actions, thus
guaranteeing that the exit distance of any FG state is at most 2. However, this method does not show that this is always
necessary, and thus does not provide a characterization of FG states according to their exit distance.
To provide such a characterization, we define an easy FG state as an FG state with exactly 2 strips such that the
rightmost strip has a size of 2. We can now show the following:
Theorem 3.2. If π is an easy FG state, then the exit distance of hG for π is 1 and h∗ (π) = 3.
Proof. Let π be an easy FG state. Since all FG states are locked, the exit distance of π is at least 1. π will also
necessarily have the following form hN − 2, ..., 1, N, N − 1i. As such, π has two gaps, one of which can be removed
3

by applying MN −1 and then MN to reach state π ′ = hN − 1, N − 2, ..., 1, N i. Applying MN −1 and then MN will
lead to state π ′ = hN − 1, N − 2, ..., 1, N i. Since π ′ has a single gap, the exit distance of π is 1.
Applying MN −1 to π ′ completes the sort of π, for a solution to π with cost 3. Since the fact that π is locked means
that h∗ (π) ≥ hG (π) + 1 ≥ 3, this solution is optimal.
Let us now contain the remaining FG states, which we call hard FG states. We now show the following:
Theorem 3.3. The exit distance of hG is 2 for any hard FG state.
Proof. Let π be a hard FG state, and let ℓ ≥ 2 be the size of the rightmost strip of π. Then π is of the form
he1 , ..., eN −ℓ , N, N − 1, ..., N − ℓ + 1i, where e1 to eN −ℓ are pancakes in the range from 1 to N − ℓ. Consider following sequence of moves: MN , Mℓ , and then MN . The result of MN will be hN − ℓ + 1, ..., N − 1, N, eN −ℓ, ..., e1 i.
Mℓ (MN (π)) will then be hN, N − 1, ..., N − ℓ1 , eN −ℓ , ..., e1 i. The final application of MN will lead to the state
he1 , ..., eN −ℓ , N − ℓ + 1, ..., N − 1, N i. The gap between locations N and N + 1 in π is now gone, while all other
gaps remain. Thus, hG (MN (MN −1 (MN (π)))) = hG (π) − 1, and so the exit distance of π is at most 2.
Let us now show that the exit distance of π is greater than 1. Since π is locked, the exit distance is at least 1. We
will now show that for any Mi , Mi (π) cannot be an exit. There are three main cases to consider.
Case 1: Mi is a gap increasing move.
Because of the consistency of hF and hG (Mi (π)) = hG (π) + 1, no neighbour of Mi (π) can have fewer than
G
h (π) gaps. As such, Mi (π) cannot be an exit in this case.
Case 2: Mi is a gap neutral move that replaces one gap with another.
Since the only gaps are between the strips, this means that location i must be the end of some strip. Suppose that
it is at the end of the first strip (i.e. i is the length of the first strip). In this case, π is of the form hi, i − 1, ..., 1, ...i and
Mi (π) will be h1, 2, ..., i...i. Pancake 1 is already on top of 2, and so Mi (π) is locked and thus cannot be an exit.
Now suppose that the size of the first strip is smaller than i. Let ℓ be the size of the strip ending at location i and
let ℓ′ be the size of the strip right before that strip. Then π is of the following form:
h..., i − ℓ, i − ℓ − 1, ..., i − ℓ − ℓ′ + 1, i, ..., i − ℓ + 2, i − ℓ + 1...i
In this state, pancake i − ℓ + 1 is in location i. Then Mi (π) will be as follows:
hi − ℓ + 1, i − ℓ + 2, ..., i, i − ℓ − ℓ′ + 1, ..., i − ℓ − 1, i − ℓ, ...i
Sinze i − ℓ + 1 is the top pancake, the only possible locations for gaps that can be removed in Mi (π) are above
pancakes i − ℓ + 2 and i − ℓ. However, these pancakes do not have gaps above them. As such, Mi (π) is locked and is
not an exit. Therefore, Mi (π) cannot be an exit if Mi is a gap neutral move that replaces one gap with another.
Case 3: Mi is a gap neutral move that replaces one adjacency with another.
Let ℓ and ℓ′ be the sizes of the first and second strips in π. By the definition of an FG state, π is of the following
form:
hℓ, ℓ − 1, ..., 1, ℓ + ℓ′ , .., ℓ + 2, ℓ + 1, ...i
In this state, ℓ + 1 is in location ℓ + ℓ′ . Since the top pancake ℓ is already adjacent to pancake ℓ − 1, the only gap
decreasing move that replaces one adjacency with another is Mℓ+ℓ′ −1 (i.e i = ℓ + ℓ′ − 1). Applying this action to π
results in the following:
hℓ + 2, ...ℓ + ℓ′ , 1, ...ℓ − 1, ℓ, ℓ + 1, ...i
Because π is a hard FG state, it is guaranteed to have at least 3 strips or a second strip with a size at least 3. If the
second strip has a size of at least 3, then the second strip in π ends in ℓ + 3, ℓ + 2, ℓ + 1 and so Mi (π) has the following
form:
hℓ + 2, ℓ + 3, ...ℓ + ℓ′ , 1, ...ℓ − 1, ℓ, ℓ + 1, ...i
4

Since ℓ + 2 is already beside ℓ + 3 and ℓ is on top of ℓ + 1, there is no gap decreasing move in Mi (π). As such, Mi (π)
is locked and so it cannot be an exit.
If the second strip of π is of size 2 (i.e. ℓ′ = 2), then there are at least 3 strips. Let ℓ′′ be the size of the third strip.
π will necessarily have the following form:
hℓ, ℓ − 1, ..., 1, ℓ + 2, ℓ + 1, ℓ + 2 + ℓ′′ , ..., ℓ + 4, ℓ + 3, ...i
We can now see that Mℓ+ℓ′ −1 (π) has the following form:
hℓ + 2, 1, ..., ℓ − 1, ℓ, ℓ + 1, ℓ + 2 + ℓ′′ , ..., ℓ + 4, ℓ + 3, ...i
ℓ + 1 and ℓ + 3 are both below pancakes that they should be adjacent to, so this state remains locked and thus cannot
be an exit. Thus, Mi (π) is not an exit whenever Mi is a gap neutral move that replaces one adjacency with another.
Since Mi (π) cannot be an exit in all cases, the exit distance of π is at least 2. This completes the proof.
The results above show that the exit distance of any pancake state is at most 2.

4 Conclusion
In this work, we have provided the complete proofs underlying a characterization of the topology of the gap heuristic.
First, we showed that there is a gap neutral move in any non-goal locked state. Then, we provided a classification that
organizes states into whether the number of gaps can be decreased in 1, 2, or 3 actions.

References
[2005] Fischer, J., and Ginzinger, S. W. 2005. A 2-Approximation Algorithm for Sorting by Prefix Reversals. In
Proceedings of the 13th Annual European Symposium (ESA), 415–425.
[2010] Helmert, M. 2010. Landmark Heuristics for the Pancake Problem. In Proceedings of the Third Annual Symposium on Combinatorial Search (SOCS).
[2005] Hoffmann, J. 2005. Where ‘Ignoring Delete Lists’ Works: Local Search Topology in Planning Benchmarks.
Journal of Artificial Intelligence Research 24:685–758.

5

