N-Queens Genetic Algorithm Solver

A high-performance C implementation of the N-Queens problem using a Genetic Algorithm (GA). This project solves the classic puzzle of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

🚀 Features

• Flexible Problem Size: Solves from standard 8×8 up to 100×100 boards.
• Genetic Algorithm Implementation:
  • Representation: Permutation encoding (ensures no row/column conflicts by design).
  • Selection: Supports both Tournament Selection and Roulette Wheel Selection.
  • Crossover: Order Crossover (OX) to maintain permutation integrity.
  • Mutation: Swap mutation to maintain genetic diversity.
  • Elitism: Preserves the best solutions across generations.
• Interactive CLI: Comprehensive menu for running experiments, tuning parameters, and comparing methods.
• Visualization: Text-based chessboard visualization for solutions.
• Performance Testing: Built-in benchmarking for large N values (20, 50, 100).

🛠️ Technical Details

Algorithm Configuration

• Genes: An array where genes[i] = row represents a queen at (row, i).
• Fitness Function: Negative count of diagonal conflicts. A fitness of 0 indicates a perfect solution.
• Default Parameters:
  • Population Size: 150
  • Mutation Rate: 5%
  • Max Generations: 2000
  • Selection: Tournament (k=3)
  • Elitism: 2 individuals

📋 Prerequisites

• C Compiler: GCC or Clang (supporting C11).
• CMake: Version 4.0 or higher.

🔨 Building the Project

You can build the project using CMake:

mkdir build
cd build
cmake ..
cmake --build .

Alternatively, compile directly with GCC:

gcc -o nqueens_solver main.c -O3

🎮 How to Use

Run the executable to enter the interactive menu:

./CS3005_Project3

Menu Options:

1. Run GA with default parameters: Quickly solve N=8.
2. Run GA with custom parameters: Configure N, population size, mutation rate, and selection method.
3. Compare selection methods: Runs a statistical comparison between Tournament and Roulette Wheel selection.
4. Test large N values: Benchmarks the algorithm against N=20, N=50, and N=100.
5. Change default parameters: Globally update settings for the current session.
6. Show best solution: Redisplay the best result found during the session.
7. Exit: Close the program.

📊 Sample Output

========================================
SOLUTION FOR N = 8
========================================
Generations used: 42
Conflicts: 0
Fitness: 0
VALID SOLUTION FOUND!

. . . . . Q . . 
. . Q . . . . . 
. . . . . . Q . 
Q . . . . . . . 
. . . . . . . Q 
. . . . Q . . . 
. Q . . . . . . 
. . . Q . . . . 

Chromosome: [5, 2, 6, 0, 7, 4, 1, 3]