Local search algorithms are very efficient in solving n-Queen problems. You are asked to implement the following two algorithms to solve the n-queen problem:

1) Straight-forward steepest-ascent hill climbing as described in our lecture "local search".

2) Your choice of one of the following algorithms: simulated annealing search algorithm ("local search" lecture); the genetic algorithm ("local search" lecture); or the MIN-CONFLICTS algorithm ("CSP" lecture).

For analysis, you should generate a large number of n-queens instances (>100) and solve them. Measure the percentage of solved problems, search costs and the average running time. Explain why you get such results, for example, why the steepest-ascent hill climbing can only solve about 14% of the problems (remember this percentage is for 8-queen, your answer might be different, smaller percentage), or what kind of improvements have you made to make your algorithms more efficient.

If you choose to implement the genetic algorithm, then your goal is to be able to solve the problem. You need to show that your program is able to solve at least three cases