When only the final state matters — not the path — local search keeps one current state and repeatedly moves to a better neighbour. It uses almost no memory and handles huge or continuous spaces, but it can get stuck.

The objective function (or cost) defines a state-space landscape. Hill climbing moves uphill (maximising) or downhill (minimising cost) until no neighbour is better.

Steepest-ascent hill climbing on 8-queens

State: one queen per column, state[c] = its row. Neighbours: move one queen within its column (8 × 7 = 56 neighbours). Cost h: pairs of queens attacking each other.

Python

def conflicts(state):                     # number of attacking pairs; 0 = solved
    n = len(state)
    return sum(1 for i in range(n) for j in range(i + 1, n)
               if state[i] == state[j] or abs(state[i] - state[j]) == j - i)

import random

def neighbours(state):
    for col in range(len(state)):
        for row in range(len(state)):
            if row != state[col]:
                yield state[:col] + (row,) + state[col + 1:]

def hill_climb(state):
    steps = 0
    while True:
        best = min(neighbours(state), key=conflicts)
        if conflicts(best) >= conflicts(state):
            return state, steps                 # no neighbour is better: a peak (or plateau)
        state, steps = best, steps + 1

random.seed(1)
start = tuple(random.randrange(8) for _ in range(8))
end, steps = hill_climb(start)
print(start, conflicts(start))             # (2, 1, 4, 1, 7, 7, 7, 6) 9
print(end, conflicts(end), steps)          # (5, 2, 4, 1, 7, 0, 3, 6) 1 4 ← stuck: a local minimum

starts = [tuple(random.randrange(8) for _ in range(8)) for _ in range(200)]
solved = sum(conflicts(hill_climb(s)[0]) == 0 for s in starts)
print(f"{solved}/200 random starts solved")    # 31/200 random starts solved

Why it gets stuck

Variants that escape

Variant	Idea	Effect on 8-queens (textbook figures)
Steepest ascent	Take the best neighbour	Solves ~14% of starts, in ~4 steps
Sideways moves	Allow up to k moves to equal-valued neighbours (plateaus)	~94% solved, ~21 steps
Stochastic hill climbing	Pick randomly among uphill moves, weighted by steepness	Slower but finds better peaks on some landscapes
First-choice	Generate random neighbours until one is better	Good when there are thousands of neighbours
Random-restart	Run from random starts until a solution appears	Complete with probability → 1; expected restarts ≈ 1/p

Python

def conflicts(state):                     # number of attacking pairs; 0 = solved
    n = len(state)
    return sum(1 for i in range(n) for j in range(i + 1, n)
               if state[i] == state[j] or abs(state[i] - state[j]) == j - i)

import random

def hill_climb(state):
    while True:
        nbrs = [state[:c] + (r,) + state[c + 1:] for c in range(8) for r in range(8) if r != state[c]]
        best = min(nbrs, key=conflicts)
        if conflicts(best) >= conflicts(state):
            return state
        state = best

def random_restart(seed):
    random.seed(seed)
    restarts = 0
    while True:
        result = hill_climb(tuple(random.randrange(8) for _ in range(8)))
        if conflicts(result) == 0:
            return result, restarts
        restarts += 1

print(random_restart(1))     # ((5, 1, 6, 0, 2, 4, 7, 3), 3)

What is the main weakness of hill climbing and how do you fix it?

How is gradient descent related to hill climbing?