N-Queens using Genetic Algorithm: A Comparative Study

This paper aims to shed light on the use of genetic algorithm to solve for the N Queens problem on values of N that are too large to compute using the simple backtracking method. The N Queens problem is where Queens are to be placed on a N*N matrix that represents a chessboard such that no two queens are able to be in contact with each other. The textbook solution for the problem is to use backtracking, a problem-solving algorithmic technique that involves finding a solution incrementally and reverting to the previous state when one route is blocked. This approach can become computationally infeasible when the value of N is too large. By implementing the solution using a genetic algorithm we see a sharp drop in the complexity and the time taken for higher values of N. We compare and contrast the approach with the backtracking method and conclude the superior efficiency of genetic algorithm for this particular problem.