Effect of Explicit Constraint by Comparative Study of Techniques for Solving N-Queens Problem

N-Queen is a well-known problem which states that for a given N x N chessboard, place N queens in such a way that no two queens can attack each other. Thus, two Queens should not lie in the same row, column or diagonal to each other. There are various approaches to solve this problem like Brute Force, Backtracking, Branch and Bound, Ant Colony Optimization, Particle Swarm Optimization, Genetic Algorithm, Dynamic Programming Solution, etc. [1]. In this paper, a comparative study and analysis of computation time required to solve N-Queen problem by Brute Force Search and Backtracking approach is done. The corresponding graph of computational time required by aforementioned two algorithms is plotted to analyze their performance. Further, a constraint is added to N-Queen problem where the position of the first queen in the first row is kept fixed. Backtracking approach is applied to the problem after addition of the constraint and its results are compared with Backtracking algorithm without any explicitly defined constraint. The graphical analysis gives insight into their performance. Thus, this paper would also provide the impact of an explicit constraint on Backtracking algorithm. General Terms Brute Force Algorithm, Backtracking Algorithm.