Hill Climbing on 8-Queens and the 8-Puzzle

Two puzzles that look alike behave very differently under hill climbing. On the 8-queens problem, a steepest-descent hill climber started from a random board solves about one instance in seven, and a few random restarts or a budget of sideways moves raise that to nearly every instance. On the 8-puzzle, the same algorithm with the textbook heuristic stops before reaching the goal on 999 of 1,000 random instances, and neither sideways moves nor a better heuristic changes the picture much. The difference says more about the problems than about the algorithm, and it is a compact lesson in when local search is the right tool.

The first assignment of CSC 742 asked for exactly this comparison: hill climbing on the 8-puzzle with the number of misplaced tiles as the heuristic, and on 8-queens with the number of attacking pairs, reporting runs that succeed and runs that get stuck, and explaining how random restarts help. The original report and code are not available, so this article rebuilds the assignment as a seeded experiment, compares it with the figures that Russell and Norvig (2020) publish for 8-queens, and adds an exhaustive analysis of the 8-puzzle. The general algorithm is described in hill climbing, and the remedies used here, sideways moves and restarts, in escaping local optima.

The two problems

8-queens. Place eight queens on a chessboard so that no two attack each other along a row, a column, or a diagonal. Russell and Norvig (2020, §4.1.1) use a complete-state formulation: every state has all eight queens on the board, one in each column, so a state is a list of eight row numbers and there are $8^8 = 16{,}777{,}216$ states. The heuristic $h$ counts the pairs of queens that attack each other, directly or through another queen in between. If $k$ queens share a row or a diagonal, they contribute $\binom{k}{2}$ pairs, so

$$h = \sum_{\ell} \binom{k_\ell}{2},$$

where the sum runs over the 8 rows and the 30 diagonals of both directions, and $k_\ell$ is the number of queens on line $\ell$. A solution has $h = 0$. A move takes one queen to another square in its own column, so every state has $8 \times 7 = 56$ neighbors.

A worked board

The board below is the state $(6, 0, 4, 3, 2, 1, 0, 2)$: the queen in column 0 is on row 6, the queen in column 1 on row 0, and so on, with row 0 at the bottom. It was chosen as the first seeded random board with $h = 17$, the same value as a well-known textbook example (Russell and Norvig, 2020, §4.1.1), though the board itself is different. Only three lines hold more than one queen:

The diagonal shows why $h$ counts indirect attacks. Six queens on one diagonal block one another, so only five pairs are adjacent along it, but the definition counts all $\binom{6}{2} = 15$ pairs. With that count, moving any one queen off a line that holds $k$ queens lowers $h$ by exactly $k - 1$, whichever queen it is, which makes the effect of a move easy to compute.

Each number in panel (b) can be checked the same way. Moving the queen of column 6 from row 0 to row 7 takes it off the long diagonal, where it was in conflict with five queens, and off row 0, where it was in conflict with one. On its new square, row 7 is empty and neither diagonal through the square in row 7, column 6 holds another queen, so it gains no conflicts, and $h = 17 - 5 - 1 = 11$. Moving the queen of column 4 to row 7 removes its five diagonal conflicts and its row-2 conflict in the same way, and also gives 11. These are the only two moves that reach 11; the 56 neighbors average 14.43, and some, such as moving the column-1 queen to row 5, make the board worse (22).

Steepest descent from this board, breaking ties with a seeded random choice, runs as follows:

The climb is typical in two ways. It is short, four moves, because each move removes several conflicts at once. And it stops at $h = 1$ with two neighbors that also have $h = 1$: this is a plateau, not a strict local minimum, so a hill climber allowed sideways moves would keep going. A strict local minimum looks like the next board, where one pair of queens attacks along a diagonal and every one of the 56 moves leaves at least two attacking pairs:

The 8-puzzle. Eight numbered tiles and a blank sit on a 3 by 3 grid. A move slides a tile adjacent to the blank into it. The goal used here has the blank in the top-left corner and the tiles 1 to 8 in reading order. Two standard heuristics estimate the distance to the goal (Russell and Norvig, 2020, §3.6): $h_1$, the number of misplaced tiles (the blank is not counted), and $h_2$, the sum over tiles of the Manhattan distance from each tile to its goal square. Both are admissible: they never overestimate the number of moves still needed, since every misplaced tile must move at least once, and every tile must travel at least its Manhattan distance, one square per move.

Not every arrangement of the tiles can reach the goal. Johnson and Story (1879) settled the question for the 15-puzzle: Johnson showed that half of the arrangements are unreachable, and Story showed that the other half can all be reached. The same parity argument works on the 3 by 3 board. Read the tiles in row order, ignoring the blank, and count inversions, pairs of tiles that appear in the wrong order. A horizontal move does not change the reading order. A vertical move carries one tile past the two tiles between its old and new positions, which changes the inversion count by $-2$, $0$, or $+2$. The parity of the inversion count never changes, so only the $9!/2 = 181{,}440$ arrangements with the goal's parity (an even count) are reachable. A breadth-first search from the goal in the experiment below visits exactly 181,440 states, which confirms that every one of them is reachable.

The experiment

The script tools/experiments/evolution/hill_climbing_puzzles.py in the site repository implements everything below in standard-library Python. Its hill climber is steepest descent: at each step it scores every neighbor and moves to one with the lowest heuristic value. Without sideways moves, it stops as soon as the best neighbor is not strictly better than the current state. With sideways moves, it may also move to a best neighbor of equal value, up to 100 consecutive times; the counter resets after each strict improvement, as in Russell and Norvig's version. A step is one move. A run succeeds when the heuristic reaches 0.

When several neighbors tie for best, the book's pseudocode moves to one of them without saying which. The script implements two rules: random tie-breaking, which picks uniformly among the best neighbors with a seeded generator, and first tie-breaking, which takes the first best neighbor in a fixed order (column 0 to 7, then row 0 to 7). The difference turns out to matter a great deal. The worked boards and puzzle states in this article, and the extra tallies of where runs stop, come from a companion script, tools/experiments/evolution/puzzles_examples.py, which reuses the same functions.

8-queens results

Each configuration ran from 30,000 random boards, in 30 seeded batches of 1,000.

Across the 30 batches, the success rate without sideways moves had a median of 14.15% (interquartile range 13.0% to 14.7%), and with sideways moves and random ties a median of 94.25% (93.7% to 94.8%). The pooled 95% confidence intervals are 13.6% to 14.4% and 94.0% to 94.5%.

Agreement with the book. Russell and Norvig (2020, §4.1.1) report that steepest-ascent hill climbing gets stuck 86% of the time, taking about 4 steps when it succeeds and 3 when it gets stuck, and that allowing up to 100 consecutive sideways moves raises the success rate to about 94%, at a cost of about 21 steps per success and 64 per failure. The success rates and the step counts without sideways moves reproduce. With sideways moves, the reproduction takes 19.16 steps on success and 60.68 on failure, with standard errors of 0.11 and 1.20, so the gaps to 21 and 64 are larger than sampling error in this experiment. The book does not state how many boards it used or exactly what it counted as a step, and its pseudocode does not fix a tie-breaking rule, so the cause of the gap cannot be pinned down from the text. What the experiment does show is that the sideways-move figure depends heavily on the tie-breaking rule, which the pseudocode leaves open.

Why tie-breaking matters. Without sideways moves, the rule barely matters: 14.02% against 14.68%, in runs only three or four steps long. With sideways moves, the rule decides the outcome. Under first tie-breaking the chosen move is a function of the state alone, so once a stretch of sideways moves returns to a state it has visited, it repeats the same loop until the budget of 100 is spent. That happened in 65.63% of all runs, which accounts for almost every failure (67.55% of runs failed), and it explains why the failures average 100.68 steps. Random tie-breaking also revisits states, in 57.91% of runs, but it does not repeat the same loop, so the walk keeps exploring the plateau, and only 3.20% of runs ended with the sideways budget exhausted. A sideways move is useful only as part of a random walk across a plateau. Deterministic sideways moves on a plateau are a cycle.

How close the failures come. Replaying the 30,000 runs without sideways moves (random ties) and recording $h$ where each run stopped shows that the failures are near misses:

More than half of the failed runs stop one attacking pair away from a solution, and 95% stop within two. And almost none of them is a strict local minimum like the board pictured above: 25,428 of the 25,793 failed runs (98.6%) stopped at a board with at least one neighbor of equal $h$, as the worked descent did, and only 365 at a board where every move makes $h$ worse. This is why sideways moves are so effective here. Nearly every failure is a plateau, and a random walk across it often reaches a board from which $h$ can fall again. (The success count, 4,207 of 30,000, is the 14.02% of the table.)

Random restarts

Random-restart hill climbing runs the hill climber from fresh random boards until one run succeeds. If each run succeeds independently with probability $p$, the number of runs needed is geometric with mean $1/p$. Russell and Norvig (2020, §4.1.1) add an expected step count: one successful run plus, on average, $(1 - p)/p$ failed ones,

$$E[\text{steps}] = s_{\text{ok}} + \frac{1 - p}{p}\, s_{\text{fail}},$$

where $s_{\text{ok}}$ and $s_{\text{fail}}$ are the mean step counts of successful and failed runs. With their figures this gives about 22 steps without sideways moves and about 25 with them. The script ran 10,000 restart trials for each setting, with random ties.

Restarts solved every trial. The geometric model fits closely, as it should, since the runs are independent. The measured restart figure with sideways moves, 23 steps rather than 25, follows from the lower per-run step counts above. The two strategies cost the same number of steps on average. Sideways moves spend their steps walking across plateaus; restarts spend them on short runs that end in local minima. Each step evaluates the same 56 neighbors either way.

The mean hides a long tail. Without sideways moves, the median trial needed 5 runs but one needed 53, and the probability of having a solution within $k$ runs is $1 - (1 - p)^k$: about 53% after 5 runs, 78% after 10, and 90% only after 16. Escaping local optima derives that formula and checks it against these trials run by run.

For larger boards, the representation matters more than these tricks. Sosič and Gu (1991) placed one queen in each row and each column from the start, as a permutation, so that only diagonal conflicts remain, and swapped pairs of queens whenever a swap reduced the number of conflicts. With a careful initial placement, their algorithm solved the 3,000,000-queens problem in about 55 seconds on an IBM RS 6000/530 workstation. Choosing a formulation that rules out most conflicts before the search begins shapes the fitness landscape the local search has to cross.

8-puzzle results

Instances

The script generated six sets of 1,000 instances. Five are random walks of $d = 4$, 8, 16, 32, and 64 moves from the goal, never undoing the previous move. The sixth draws uniformly from all solvable states, by shuffling the tiles and keeping a permutation only if its inversion count is even. A random walk of $d$ moves is not an instance at distance $d$: short walks reach few distinct states, and long walks partly undo themselves, so the table gives the true optimal solution lengths, taken from the breadth-first search.

The table gives the percentage of instances that steepest-descent hill climbing solved, with random tie-breaking. One depth-32 walk happened to end at the goal itself, and it is counted as solved. Beyond the shallowest scrambles, hill climbing almost never solves the 8-puzzle with either heuristic.

Why it fails: an exhaustive count

The state space is small enough to examine completely. The breadth-first search gives the exact distance of every state from the goal: the largest is 31 moves, and the mean is 21.97. The script then scores every move from every state, 483,840 moves in all.

Plateaus dominate $h_1$. A move changes the position of exactly one tile, so $h_1$ changes only if that tile leaves its goal square or enters it. Most moves do neither, and 77% of all moves leave $h_1$ unchanged. In 69% of non-goal states no move lowers $h_1$, so a hill climber without sideways moves stops on its first step. Sideways moves let it wander these plateaus, which helps a little (11.4% to 29.1% at depth 8), but the solutions it finds are longer than necessary: at depth 16 the solved runs took 16.5 more steps than the optimal solution, on average.

$h_2$ has no plateaus, only local minima. The moved tile goes one square closer to its goal square or one square farther away, so every move changes $h_2$ by exactly 1. The budget of sideways moves is never used, and the script's runs with and without it are identical. The fitness landscape of $h_2$ has no flat regions at all, yet a quarter of all states are local minima, where every move leads uphill.

A single state shows how this happens. Take

$$\begin{array}{ccc} \_ & 1 & 5 \\ 3 & 7 & 4 \\ 2 & 6 & 8 \end{array}$$

which is 12 moves from the goal. Five tiles are misplaced (5, 7, 4, 2 and 6), so $h_1 = 5$. Their Manhattan distances are 1 for tile 5 (one row too high), 1 for 7, 1 for 4, 4 for 2 (two rows and two columns from its goal in the top-right corner), and 1 for 6, so $h_2 = 8$. The blank is in a corner, so there are only two moves, and both raise $h_2$ to 9:

The second move is on an optimal path, so the optimal solution must begin by making $h_2$ worse. A heuristic that underestimates the distance by 4, as $h_2$ does here, leaves room for such detours, and strict descent cannot take them.

The exhaustive count also shows how the problem grows with the distance to the goal. Panel (a) of the next figure plots the mean of each heuristic against the true distance. Both stay below the diagonal, as admissibility requires, but $h_1$ levels off near 7 (it cannot exceed 8), while $h_2$ keeps rising at a little over half the true distance. Panel (b) plots the share of states at each distance where no move improves the heuristic, so that strict descent stops at its first step.

The zigzag in panel (b) has a simple cause. Every move carries the blank to an adjacent square, so, colouring the board like a chessboard, the blank changes colour at every move. The goal has the blank in a corner, so at even distances the blank is on a corner or the centre, and at odd distances on an edge square. A blank in a corner has only two moves and a blank on an edge has three, and fewer moves means fewer chances that one of them improves $h$. Over all non-goal states, the share with no improving move under $h_2$ is 47.3% with the blank in a corner, 7.3% with it on an edge, and 1.2% with it in the centre, where it has four moves; under $h_1$ the shares are 81.2%, 62.5%, and 50.0%.

Strict descent can only succeed where the heuristic is exact. Each move changes either heuristic by at most 1. A run without sideways moves lowers $h$ by exactly 1 at every step, so if it reaches the goal it does so in exactly $h(s)$ moves from its start $s$. That path is a solution, so the optimal length $h^*(s)$ is at most $h(s)$; admissibility gives $h(s) \le h^*(s)$; so $h(s) = h^*(s)$. Strict hill climbing can therefore succeed only from the states where the heuristic is exactly right: 78 states for $h_1$ and 2,350 for $h_2$, out of 181,439. The condition is necessary but not sufficient, since a random tie-break can still step into a state where the heuristic underestimates. It explains both the collapse of the success rate beyond the shallowest scrambles and why every success without sideways moves in the experiment was an optimal solution.

A* with the same heuristics

The same heuristics that fail as hill-climbing objectives work well as guides for systematic search. A expands states in order of $g + h$, the cost so far plus the heuristic, and with an admissible heuristic it returns an optimal solution (Russell and Norvig, 2020, §3.5.2). Both heuristics are also consistent, as the graph-search version in the script requires: a move costs 1 and changes either heuristic by at most 1. On the first 100 instances of every set, A with either heuristic solved all of them, and every solution length matched the breadth-first distance.

Here the better heuristic pays off directly: on uniform random instances, $h_2$ expands about a tenth as many nodes as $h_1$. A* never gets stuck, because it keeps every unexpanded state on its frontier and can always go back. Hill climbing keeps only the current state, so when its one candidate path runs into a local minimum, nothing remains to fall back on.

What the two problems teach

Local search suits problems where only the final state matters. In 8-queens, any arrangement with no attacks is a solution, and the path to it is irrelevant. In the 8-puzzle, the start state is fixed and the sequence of moves is the answer. Russell and Norvig (2020, §4.1) draw the same distinction: local search is designed for problems in which the path to a goal does not matter. The 8-puzzle can be forced into the local-search mold, as the assignment did, but it is a path-finding problem.

Restarts need a problem that can be restarted. For 8-queens, a fresh random board is another valid starting point, and with $p = 0.14$ a solution arrives after about seven runs. For an 8-puzzle instance, a fresh random state is a different instance. Repeating runs from the same start state with random tie-breaking can still help, but without sideways moves only from the small set of states where descent can succeed at all.

The heuristic shapes the search space. For A*, $h_2$ beats $h_1$ simply by being larger, since both are admissible. For hill climbing, what matters is the shape of the surface: $h_1$ is mostly flat, and $h_2$ has no flat regions but many pits. The same function can be a good estimate of distance and a poor objective for local search. Each heuristic, together with the move set, defines its own fitness landscape, a point that fitness landscapes makes about variation operators.

Sideways moves are a random walk, and they need randomness. On 8-queens, 100 sideways moves raise the success rate from 14% to 94% with random tie-breaking, and only to 32% with a fixed tie-breaking rule, because deterministic sideways moves cycle. On the 8-puzzle under $h_1$, they help a little and lengthen the solutions. Under $h_2$, which has no plateaus, they do nothing.

These are the problems that the rest of the course addresses with populations. A genetic algorithm keeps many candidates rather than one, which is a different answer to the same question that restarts and sideways moves answer: how to keep searching after the nearest local optimum.

References

• Johnson, W. W., and Story, W. E. (1879). Notes on the "15" puzzle. American Journal of Mathematics, 2(4), 397–404.
• Russell, S., and Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4th ed., sections 3.5.2, 3.6, 4.1, and 4.1.1. Pearson.
• Sosič, R., and Gu, J. (1991). 3,000,000 queens in less than one minute. ACM SIGART Bulletin, 2(2), 22–24.