This code is a Python implementation of three different algorithms—Steepest-Ascent...

June 28, 2025 at 09:00 PM

import random, math, time

### --- Utility Functions --- ###
def generate_board():
    return [random.randint(0, 7) for _ in range(8)]

def compute_conflicts(board):
    conflicts = 0
    for i in range(8):
        for j in range(i + 1, 8):
            if board[i] == board[j] or abs(board[i] - board[j]) == abs(i - j):
                conflicts += 1
    return conflicts

def print_board(board):
    for r in range(8):
        row = ""
        for c in range(8):
            row += "Q " if board[c] == r else ". "
        print(row)
    print()

def get_neighbors(board):
    neighbors = []
    for col in range(8):
        for row in range(8):
            if board[col] != row:
                new_board = list(board)
                new_board[col] = row
                neighbors.append(new_board)
    return neighbors

def steepest_ascent_hill_climbing(board): #method to perform the hill climbing algorithm
    steps = 0
    while True:
        current_conflicts = compute_conflicts(board)
        neighbors = get_neighbors(board)
        best_board = min(neighbors, key=compute_conflicts)
        best_conflicts = compute_conflicts(best_board)
        if best_conflicts >= current_conflicts:
            return board, current_conflicts, steps
        board = best_board
        steps += 1

def simulated_annealing(board, max_steps=100000): #method to compute the simulated annealing algorithm
    temp = 1.0
    cooling = 0.003
    steps = 0

    for _ in range(max_steps):
        temp *= (1 - cooling)
        if temp <= 0:
            break
        currentConflicts = compute_conflicts(board)
        if currentConflicts == 0:
            return board, 0, steps
        neighbors = get_neighbors(board)
        next_board = random.choice(neighbors)
        delta_e = compute_conflicts(board) - compute_conflicts(next_board)
        if delta_e > 0 or random.random() < math.exp(delta_e / temp):
            board = next_board
        steps += 1

    return board, compute_conflicts(board), steps

#beginning methods for genetic algorithm
POP_SIZE = 100
MAX_GENERATIONS = 1000
MUTATION_RATE = 0.2
TOURNAMENT_SIZE = 5

def random_individual():
    individual = list(range(8))
    random.shuffle(individual)
    return individual

def ga_fitness(individual):
    max_pairs = 28  #total non-attacking pairs
    conflicts = 0
    for i in range(8):
        for j in range(i+1, 8):
            if abs(individual[i] - individual[j]) == abs(i - j):
                conflicts += 1
    return max_pairs - conflicts

def tournament_selection(population):
    candidates = random.sample(population, TOURNAMENT_SIZE)
    return max(candidates, key=ga_fitness)

def crossover(parent1, parent2):
    start, end = sorted(random.sample(range(8), 2))
    child = [None] * 8
    child[start:end] = parent1[start:end]
    fill = [gene for gene in parent2 if gene not in child[start:end]]
    idx = 0
    for i in range(8):
        if child[i] is None:
            child[i] = fill[idx]
            idx += 1
    return child

def mutate(individual):
    if random.random() < MUTATION_RATE:
        i, j = random.sample(range(8), 2)
        individual[i], individual[j] = individual[j], individual[i]

def genetic_algorithm():  #genetic algorithm is more separate from the other two, doesn't use initial list
    population = [random_individual() for _ in range(POP_SIZE)]
    generation = 0
    while generation < MAX_GENERATIONS:
        population.sort(key=ga_fitness, reverse=True)
        if ga_fitness(population[0]) == 28:
            return population[0], 0, generation
        new_population = []
        while len(new_population) < POP_SIZE:
            p1 = tournament_selection(population)
            p2 = tournament_selection(population)
            child = crossover(p1, p2)
            mutate(child)
            new_population.append(child)
        population = new_population
        generation += 1
    return None, 1, generation

def trialRunner(trials=100):
    print(f"Running {trials} trials per algorithm for N={8}")

    #generating the list of boards that hill climbing and simulated annealing will attempt to solve, helps with comparison
    boards = set()
    while len(boards) < trials:
        b = tuple(generate_board())
        boards.add(b)
    boards = [list(b) for b in boards]

    def evaluate(algorithm_fn, label, use_board=True):
        success = 0
        totalSteps = 0
        runtime = 0
        for board in boards:
            start = time.time()
            if use_board:
                result, conf, steps = algorithm_fn(board)
            else:
                result, conf, steps = algorithm_fn()
            end = time.time()
            if conf == 0:
                success += 1
                totalSteps += steps
                runtime += end - start
        print(f"\n{label} Results:")
        print(f"  Solved: {success}/{trials}")
        if success:
            print(f"  Avg Steps/Gen: {totalSteps/success:.2f}")
            print(f"  Avg Time: {runtime/success:.4f} sec")
        else:
            print("  No successful solutions.")
    start = time.time()
    evaluate(steepest_ascent_hill_climbing, "Hill Climbing", use_board=True)
    end = time.time()
    totalTime = end - start
    print(f"Hill Climbing Total Runtime: {totalTime}")
    start = time.time()
    evaluate(simulated_annealing, "Simulated Annealing", use_board=True)
    end = time.time()
    totalTime = end - start
    print(f"Simulated Annealing Total Runtime: {totalTime}")
    start = time.time()
    evaluate(genetic_algorithm, "Genetic Algorithm", use_board=False)
    end = time.time()
    totalTime = end - start
    print(f"Genetic Algorithm Total Runtime: {totalTime}")

def main():
    trialRunner()

    #Print the sample solved genetic solution
    print("\nSample Genetic Algorithm Solution:")
    solution, _, _ = genetic_algorithm()
    if solution:
        print_board(solution)

if __name__ == "__main__":
    main()

This code is a Python implementation of three different algorithms—Steepest-Ascent Hill Climbing, Simulated Annealing, and a Genetic Algorithm—to solve the 8-Queens problem. The 8-Queens problem is a classic constraint satisfaction problem in which you attempt to place 8 queens on a standard chessboard (8x8 grid) such that no two queens threaten each other. Queens threaten each other if they are in the same row, column, or diagonal.

Here's a breakdown of the code:

1. Utility Functions

generate_board(): Generates a random initial board representing a possible solution to the 8-Queens problem. Each element in the board represents a queen's row position for each column.
compute_conflicts(board): Calculates the number of conflicts for a given board configuration. A conflict indicates that two queens threaten each other.
print_board(board): Prints a visual representation of the chessboard, marking queens (Q) and open spaces (.).
get_neighbors(board): Generates all possible boards (neighbors) by moving each queen to every other row in its respective column.

2. Steepest-Ascent Hill Climbing

steepest_ascent_hill_climbing(board):
- Implements the hill climbing search algorithm.
- Starting from a given board, it evaluates all its neighbors and selects the one with the fewest conflicts.
- Continues iteratively until no neighbor is better than the current board.
- Returns either a solution (conflicts = 0) or the best-found configuration along with the number of steps.

Hill Climbing Characteristics:

Fast but prone to getting stuck in local minima.

3. Simulated Annealing

simulated_annealing(board, max_steps=100000):
- Implements simulated annealing, a probabilistic search algorithm that can escape local minima.
- Starts with a high "temperature" that progressively cools down.
- At each step, a random neighbor is chosen, and acceptance is determined by the difference in conflicts and the current temperature.
- If the difference is favorable (or a random chance based on the temperature allows it), the neighbor is accepted as the new state.
- Runs for a max number of steps or until a solution is found.

Simulated Annealing Characteristics:

More likely to find a global solution compared to Hill Climbing, but it may take more time.

4. Genetic Algorithm

random_individual(): Generates a random individual/board for the population, with one queen per column.
ga_fitness(individual): Evaluates the fitness of an individual based on the number of non-attacking queen pairs. The maximum fitness is 28 (as there are 28 possible unique pairs of queens).
tournament_selection(population): Selects the fittest individual from a subset of the population using a tournament selection strategy.
crossover(parent1, parent2): Combines two parent solutions into a child solution using genetic crossover. It partially inherits rows from one parent and fills the rest from the other.
mutate(individual): Randomly swaps two queen positions in an individual based on a mutation rate.
genetic_algorithm():
- Implements a genetic algorithm to solve the 8-Queens problem.
- Begins with a random population and iteratively improves via selection, crossover, and mutation.
- Stops when an individual with fitness 28 is found or when the maximum generation limit is reached.

Genetic Algorithm Characteristics:

Optimized for global exploration and can often find a solution even in highly complex problem spaces.
Slower compared to Hill Climbing or Simulated Annealing.

5. Trial Running and Evaluation

trialRunner(trials=100):
- Runs the three algorithms (steepest_ascent_hill_climbing, simulated_annealing, and genetic_algorithm) for a specified number of trials.
- For Hill Climbing and Simulated Annealing, trials start with randomly generated boards.
- For the Genetic Algorithm, trials begin with a randomly generated population.
- Tracks and reports metrics:
  - Success rate (how many trials solved the problem).
  - Average number of steps/time per successful trial.
  - Total runtime for all trials.

6. Program Execution

main():
- Runs the trialRunner() function to evaluate the performance of all algorithms.
- Finally, prints a sample solution found using the Genetic Algorithm.

Summary

This code evaluates and compares three search algorithms (Hill Climbing, Simulated Annealing, and Genetic Algorithm) to solve the 8-Queens problem. The algorithms utilize different strategies to find solutions and are benchmarked in terms of success rate, speed, and efficiency.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr