1 IntroductionThe N-Queens problem is a classical AI problem. Its name is derived from the allowed moves for the queen piece in chess. Queens are allowed to move horizontally, vertically, or diagonally, backward and forward, with the only restriction being that they can move in only one direction at a time. A queen that can reach another piece in one move captures it.The N-Queens problem is based on the notion of trying to place N queens on an N x N grid, such that no queen will be able to capture any other queen. The N-queens problem is typical of many combinatorial problems, in that it is simple to state and relatively easy to solve for small N, but becomes difficult with a large N. Th ...view middle of the document...
A whole new population of possible solutions is thus produced by selecting the best individuals from the current "generation", and mating them to produce a new set of individuals. This new generation contains a higher proportion of the characteristics possessed by the good members of the previous generation. In this way, over many generations, good characteristics are spread throughout the population, being mixed and exchanged with other good characteristics as they go. By favouring the mating of the more fit individuals, the most promising areas of the search space are explored. If the genetic algorithm has been designed well, the population will converge to an optimal solution to the problem.The power of genetic algorithms come from the fact that the technique is robust, and can deal successfully with a wide range of problem areas, including those which are difficult for other methods to solve. Genetic algorithms are not guaranteed to find the global optimum solution to a problem, but they are generally good at finding "acceptably good" solutions to problems "acceptably quick". Where specialized techniques exist for solving particular problems, they are likely to out-perform genetic algorithms in both speed and accuracy of the final result. The main ground for genetic algorithms, then, is in difficult areas where no such techniques exist. Even where existing techniques work well, improvements have been made by hybridizing them with a genetic algorithm.Before a genetic algorithm can be run, a suitable representation for the problem must be devised. A fitness function also required to assign a figure of merit to each coded solution. As a summary, the procedures of genetic algorithms are as below:1. generate initial population2. compute fitness of each individual3. select individuals for mating4. mate individuals to produce offspring5. mutate offspring6. insert offspring into population7. if stopping criteria satisfied, go to "8", else go to "3"8. finishFigure 1: The procedures of genetic algorithms2 Implementation Decisions2.1 Genetic AlgorithmFirst of all, we need to choose a genetic algorithm from GAlib package. There are four kinds of genetic algorithm available. They are GADemeGA, GAIncrementalGA, GASimpleGA and GASteadyStateGA. It is alright to choose anyone of them. To make things simple, GASimpleGA was chosen.2.2 RepresentationAfter that, we need to define a representation for the N-queens problem. There are two ways to do that. The usual way is to represent it as a 2-dimensional binary array as shown at figure 2b. We are sure that no 2 queens will be in the same row and no 2 queens in the same column. So, for optimal solution, we can just represent the chessboard as a 1-dimensional integer array as shown at figure 2c. The number "X" in the array will represent there is a queen at row "X".For 2-dimensional binary array chessboard, there are in total (NxN)!/(N!x(N(N-1))!) = 64! / (8!56!) = 4426165368 permutations. However, fo...
