Local search: hill climbing for the 8-queens puzzle
Improve a complete state step by step, and use restarts to escape local optima.
def conflicts(board):
n = len(board)
return sum(
1
for i in range(n)
for j in range(i + 1, n)
if board[i] == board[j] or abs(board[i] - board[j]) == j - i
)
def hill_climb(board):
board = list(board)
while True:
current = conflicts(board)
best, best_move = current, None
for col in range(len(board)):
original = board[col]
for row in range(len(board)):
if row != original:
board[col] = row
score = conflicts(board)
if score < best:
best, best_move = score, (col, row)
board[col] = original
if best_move is None:
return board, current
board[best_move[0]] = best_move[1]
state = 1
def next_start(n=8):
global state
board = []
for _ in range(n):
state = (state * 1103515245 + 12345) % 2**31
board.append((state >> 16) % n)
return board
restarts = 0
while True:
board, score = hill_climb(next_start())
if score == 0:
break
restarts += 1
print(restarts, board, score)5 [0, 4, 7, 5, 2, 6, 1, 3] 0
Explanation
Local search keeps a single current state and tries to improve it by moving to a neighbouring state. It does not remember the path. That makes it very memory-efficient and useful for problems where the goal state matters but the route does not, such as placing queens, scheduling, and optimization.
In steepest-ascent hill climbing the algorithm evaluates all neighbours and moves to the best one, stopping when none is better. It can get stuck at a local optimum, a state better than all its neighbours but not a global solution, or wander on a plateau of equal values. Random restarts address this: run hill climbing from several random starting states until one succeeds. Other methods such as simulated annealing sometimes accept worse moves on purpose to escape local optima.
In the 8-queens puzzle the state lists, for each column, the row of its queen, and the cost is the number of attacking pairs. A move shifts one queen within its column. A single climb from a random board often stalls with a few conflicts left, and the program restarts from new boards until a climb reaches zero conflicts. The starts come from a small linear congruential generator written into the program so the result is identical on every machine. It succeeds after 5 failed climbs and prints a valid arrangement.
Explore the dry run
def conflicts(board): n = len(board) return sum( 1 for i in range(n) for j in range(i + 1, n) if board[i] == board[j] or abs(board[i] - board[j]) == j - i ) def hill_climb(board): board = list(board) while True: current = conflicts(board) best, best_move = current, None for col in range(len(board)): original = board[col] for row in range(len(board)): if row != original: board[col] = row score = conflicts(board) if score < best: best, best_move = score, (col, row) board[col] = original if best_move is None: return board, current board[best_move[0]] = best_move[1] state = 1 def next_start(n=8): global state board = [] for _ in range(n): state = (state * 1103515245 + 12345) % 2**31 board.append((state >> 16) % n) return board restarts = 0while True: board, score = hill_climb(next_start()) if score == 0: break restarts += 1print(restarts, board, score)Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Two queens attack each other if they share a row or a diagonal; columns are distinct by construction. | — | — | |
| Steepest ascent: remember the neighbour with the fewest conflicts. | — | — | |
| No neighbour is better: the climb stops, possibly at a local optimum with conflicts left. | — | — | |
| That climb ended with conflicts, so try again from a new starting board: random restarts. | 5 climbs failed | — | |
| The sixth start reaches a board with 0 conflicts: a valid solution. | 5 climbs failed | 5 [0, 4, 7, 5, 2, 6, 1, 3] 0 |
Cost and common mistakes
One step evaluates n × (n − 1) neighbours at O(n²) each. The number of steps and restarts varies; for 8-queens, a climb from a random board succeeds only a minority of the time.
- Hill climbing is incomplete: it can stop at a local optimum or a plateau even when a solution exists.
- Local search gives a final state, not a path. It is unsuitable when you need the sequence of actions.
- The restart count depends on the generator and its seed. The solved board is verified by its zero conflicts, not by matching an expected arrangement.
Try it yourself
Why do random restarts help hill climbing?
Reveal answer and reasoning
Each start explores a different part of the state space. Even if most climbs end in local optima, one that begins in the basin of a solution reaches it.