Performance comparison of genetic algorithms with traditional search techniques on the N-Queen Problem

This paper presents an analysis of solving the N-Queen problem using a genetic algorithm and compares its performance with traditional search algorithms like breadth-first search (BFS) and depth-first search (DFS). The N-Queen problem is a famous problem in the field of artificial intelligence that has been studied in depth. The genetic algorithm is an optimization algorithm inspired by the process of natural selection and evolution in living organisms. BFS and DFS are classical search algorithms that explore the search space to find a solution. This paper discusses all the main components of the genetic algorithm, such as population generation, fitness function, selection, crossover, and mutation, and also explains how it is used to solve the N-Queen problem. Traditional search methods, i.e., BFS and DFS, are also briefly discussed. The experimental results show that classical searching approaches are better for small-sized problems, but the genetic algorithm outperforms BFS and DFS in computation time for medium and large-sized problems. This paper concludes by analyzing the effect of parameter tuning on the genetic algorithm and suggests possible future work in the field.

I. Introduction

The N-Queen problem is a classical problem in the field of artificial intelligence [1]. In the game of chess, a queen can move in its row, column, or diagonal from its existing cell both in a forward and in backward direction. The solution to the problem is to place N queens on an N x N chessboard such that no queen is being attacked by another queen. Hence, to determine a valid solution for the N-Queen problem, there should not be two queens in the same row, column, or diagonal. This also means that there should be only one queen in each row, column, and its diagonal in the valid solution.