Project Summary

This is just an uni assignment and should not be taken seriously

This project explores the classic N-Queens problem by implementing and analyzing four different algorithmic solutions in Go. The goal is to place N chess queens on an N×N board so that no two queens can attack each other. This serves as an excellent case study for comparing the performance, scalability, and trade-offs of various search and optimization techniques.

The application includes a benchmarking suite that measures execution time and memory usage for each algorithm across different board sizes, providing clear, empirical data on their effectiveness.

Features

• Four Distinct Algorithms: Implements Exhaustive Search, Greedy Hill Climbing, Simulated Annealing, and a Genetic Algorithm.
• Performance Benchmarking: A built-in framework in main.go tests each algorithm’s speed and memory footprint.
• Scalability Analysis: Designed to demonstrate how each algorithm’s performance changes as the problem size (N) increases.
• Clear Visual Output: Renders solved boards in the terminal for easy verification and visualization.

Algorithms Implemented

The core of the project is the implementation of these four approaches:

1. Exhaustive Search (Backtracking)

A complete, depth-first search algorithm that is guaranteed to find a solution if one exists. It systematically explores every possible placement, backtracking when a conflict is found. While reliable, its O(N!) time complexity makes it impractical for larger values of N.

2. Greedy Hill Climbing

A local search heuristic that starts with a random board configuration and iteratively makes the single best move (the one that reduces the most conflicts). To escape local optima, it employs random restarts when no further improvements can be made.

3. Simulated Annealing

A more advanced probabilistic optimization technique. It starts with a high “temperature,” allowing it to accept “bad” moves to escape local optima. As the temperature gradually cools, it becomes more selective, eventually converging on a high-quality solution. This implementation includes multiple restarts and intelligent neighbor generation for better performance.

4. Genetic Algorithm

An evolutionary algorithm that maintains a “population” of potential solutions. It uses concepts from natural selection—like crossover, mutation, and elite preservation—to evolve the population over many generations toward a conflict-free solution. This approach is particularly effective for very large and complex problem instances.

Technologies

• Go (Golang): The entire project is built in Go, leveraging its simplicity and performance for computationally intensive tasks.
• Standard Library: Utilizes Go’s built-in runtime and time packages for accurate performance and memory profiling.
• Algorithm Design: Demonstrates the practical application of fundamental computer science algorithms (backtracking, local search, probabilistic optimization, evolutionary computation).
• Object-Oriented Principles: Each solver is encapsulated in its own struct with a common interface (Solve, GetSolution, PrintSolution), making the system modular and extensible.