Question

In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen.

Question: Using Hill Climbing (HC) algorithms, how many steps are needed to find the solution for the 12-Queens Problem? What is it? Draw on an 12x12 table. Show your steps.

Answer 1

The N Queen is a problem of placing N chess queens on NxN chessboard such that no 2 queens attack each other.

Algorithm :

1. Start with a random state/ configuration of the board.

2. Scan through all possible neighbours of current state and jump to the highest neighbour with highest objective value. If there's none, exit.

3. Repeat step 2 until reaching a state which is strictly higher than all neighbours. Go to step 4.

4. State is either local or global optimum.

5. Output the state and return.

Following the above algorithm, For N=12,

Output ( the 12x12 table) :

000000000010

000000010000

000010000000

010000000000

000100000000

000000100000

000000000100

000000000001

100000000000

001000000000

000001000000

000000001000

As can be seen, the 12 queens have been placed in a way such that no 2 queens are attacking each other. So, the output is correct.

Thus, it will take 12 steps to solve the 12-queens problem.