Local search: hill climbing for the 8-queens puzzle
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.
Python
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)