The goal of the 8-queens problem is to place eight queens on a chessboard such that no queen attacks any other. The queen attacks any piece in the same row, column or diagonal. The algorithms we use here are:
- Hill-climbing search : We first take an objective function - in this case it is the number of attacking pairs of queens. So, this algorithm simply moves in the direction of the decreasing(as we took number of attacking pairs as our function, this value needs to decrease to obtain a good solution) value of the function. This algorithm is a local search algorithm and does not maintain any search tree, as attaining the goal is important, but not the path to it. But the hill-climbing algorithm only gives the local mimimum, once it sees the objective function decreasing, it stops the search. We may not attain the best solution with this algorithm as it does not give the global minimum.
- Genetic alogirthm : In the genetic algorithm, the successor states are generated by combining two parent states. We assign a fitness function to each state,and the probability of selecting a state increases with its fitness function. Hence, when two parent states are selected, a random crossover point is chosen, and two successor states are generated each with the positions of the parent states on either side of the crossover point. Finally, a mutation position is chosen and is replaced with a random value.