# N-Queen Problem | Local Search using Hill climbing with random neighbour

The **N** Queen is the problem of placing **N** chess queens on an **N×N** chessboard so that no two queens attack each other.

For example, the following is a solution for **8** Queen problem.

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 4Output:

0 1 0 0

0 0 0 1

1 0 0 0

0 0 1 0Explanation:

The Position of queens are:

1 – {1, 2}

2 – {2, 4}

3 – {3, 1}

4 – {4, 3}

As we can see that we have placed all 4 queens

in a way that no two queens are attacking each other.

So, the output is correct

Input:N = 8Output:

0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 1

0 0 0 0 1 0 0 0

**Approach:** The idea is to use Hill Climbing Algorithm.

- While there are algorithms like Backtracking to solve N Queen problem, let’s take an AI approach in solving the problem.
- It’s obvious that AI does not guarantee a globally correct solution all the time but it has quite a good success rate of about 97% which is not bad.
- A description of the notions of all terminologies used in the problem will be given and are as follows:-
**Notion of a State**– A state here in this context is any configuration of the N queens on the N X N board. Also, in order to reduce the search space let’s add an additional constraint that there can only be a single queen in a particular column. A state in the program is implemented using an array of length N, such that if**state[i]=j**then there is a queen at column index**i**and row index**j**.**Notion of Neighbours**– Neighbours of a state are other states with board configuration that differ from the current state’s board configuration with respect to the position of only a single queen. This queen that differs a state from its neighbour may be displaced anywhere in the same column.**Optimisation function or Objective function**– We know that local search is an optimization algorithm that searches the local space to optimize a function that takes the state as input and gives some value as an output. The value of the objective function of a state here in this context is the number of pairs of queens attacking each other. Our goal here is to find a state with the minimum objective value. This function has a maximum value of NC2 and a minimum value of 0.

**Algorithm:**

- Start with a random state(i.e, a random configuration of the board).
- Scan through all possible neighbours of the current state and jump to the neighbour with the highest objective value, if found any. If there does not exist, a neighbour, with objective strictly higher than the current state but there exists one with equal then jump to any random neighbour(escaping shoulder and/or local optimum).
- Repeat step 2, until a state whose objective is strictly higher than all it’s neighbour’s objectives, is found and then go to step 4.
- The state thus found after the local search is either the local optimum or the global optimum. There is no way of escaping local optima but adding a random neighbour or a random restart each time a local optimum is encountered increases the chances of achieving global optimum(the solution to our problem).
- Output the state and return.

- It is easily visible that the global optimum in our case is 0 since it is the minimum number of pairs of queens that can attack each other. Also, the random restart has a higher chance of achieving global optimum but we still use random neighbour because our problem of N queens does not has a high number of local optima and random neighbour is faster than random restart.
**Conclusion:****Random Neighbour**escapes shoulders but only has a little chance of escaping local optima.**Random Restart**both escapes shoulders and has a high chance of escaping local optima.

Below is the implementation of the Hill-Climbing algorithm:

## CPP

`// C++ implementation of the` `// above approach` `#include <iostream>` `#include <math.h>` `#define N 8` `using` `namespace` `std;` `// A utility function that configures` `// the 2D array "board" and` `// array "state" randomly to provide` `// a starting point for the algorithm.` `void` `configureRandomly(` `int` `board[][N],` ` ` `int` `* state)` `{` ` ` `// Seed for the random function` ` ` `srand` `(` `time` `(0));` ` ` `// Iterating through the` ` ` `// column indices` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Getting a random row index` ` ` `state[i] = ` `rand` `() % N;` ` ` `// Placing a queen on the` ` ` `// obtained place in` ` ` `// chessboard.` ` ` `board[state[i]][i] = 1;` ` ` `}` `}` `// A utility function that prints` `// the 2D array "board".` `void` `printBoard(` `int` `board[][N])` `{` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `cout << ` `" "` `;` ` ` `for` `(` `int` `j = 0; j < N; j++) {` ` ` `cout << board[i][j] << ` `" "` `;` ` ` `}` ` ` `cout << ` `"\n"` `;` ` ` `}` `}` `// A utility function that prints` `// the array "state".` `void` `printState(` `int` `* state)` `{` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `cout << ` `" "` `<< state[i] << ` `" "` `;` ` ` `}` ` ` `cout << endl;` `}` `// A utility function that compares` `// two arrays, state1 and state2 and` `// returns true if equal` `// and false otherwise.` `bool` `compareStates(` `int` `* state1,` ` ` `int` `* state2)` `{` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `if` `(state1[i] != state2[i]) {` ` ` `return` `false` `;` ` ` `}` ` ` `}` ` ` `return` `true` `;` `}` `// A utility function that fills` `// the 2D array "board" with` `// values "value"` `void` `fill(` `int` `board[][N], ` `int` `value)` `{` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `for` `(` `int` `j = 0; j < N; j++) {` ` ` `board[i][j] = value;` ` ` `}` ` ` `}` `}` `// This function calculates the` `// objective value of the` `// state(queens attacking each other)` `// using the board by the` `// following logic.` `int` `calculateObjective(` `int` `board[][N],` ` ` `int` `* state)` `{` ` ` `// For each queen in a column, we check` ` ` `// for other queens falling in the line` ` ` `// of our current queen and if found,` ` ` `// any, then we increment the variable` ` ` `// attacking count.` ` ` `// Number of queens attacking each other,` ` ` `// initially zero.` ` ` `int` `attacking = 0;` ` ` `// Variables to index a particular` ` ` `// row and column on board.` ` ` `int` `row, col;` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// At each column 'i', the queen is` ` ` `// placed at row 'state[i]', by the` ` ` `// definition of our state.` ` ` `// To the left of same row` ` ` `// (row remains constant` ` ` `// and col decreases)` ` ` `row = state[i], col = i - 1;` ` ` `while` `(col >= 0` ` ` `&& board[row][col] != 1) {` ` ` `col--;` ` ` `}` ` ` `if` `(col >= 0` ` ` `&& board[row][col] == 1) {` ` ` `attacking++;` ` ` `}` ` ` `// To the right of same row` ` ` `// (row remains constant` ` ` `// and col increases)` ` ` `row = state[i], col = i + 1;` ` ` `while` `(col < N` ` ` `&& board[row][col] != 1) {` ` ` `col++;` ` ` `}` ` ` `if` `(col < N` ` ` `&& board[row][col] == 1) {` ` ` `attacking++;` ` ` `}` ` ` `// Diagonally to the left up` ` ` `// (row and col simultaneously` ` ` `// decrease)` ` ` `row = state[i] - 1, col = i - 1;` ` ` `while` `(col >= 0 && row >= 0` ` ` `&& board[row][col] != 1) {` ` ` `col--;` ` ` `row--;` ` ` `}` ` ` `if` `(col >= 0 && row >= 0` ` ` `&& board[row][col] == 1) {` ` ` `attacking++;` ` ` `}` ` ` `// Diagonally to the right down` ` ` `// (row and col simultaneously` ` ` `// increase)` ` ` `row = state[i] + 1, col = i + 1;` ` ` `while` `(col < N && row < N` ` ` `&& board[row][col] != 1) {` ` ` `col++;` ` ` `row++;` ` ` `}` ` ` `if` `(col < N && row < N` ` ` `&& board[row][col] == 1) {` ` ` `attacking++;` ` ` `}` ` ` `// Diagonally to the left down` ` ` `// (col decreases and row` ` ` `// increases)` ` ` `row = state[i] + 1, col = i - 1;` ` ` `while` `(col >= 0 && row < N` ` ` `&& board[row][col] != 1) {` ` ` `col--;` ` ` `row++;` ` ` `}` ` ` `if` `(col >= 0 && row < N` ` ` `&& board[row][col] == 1) {` ` ` `attacking++;` ` ` `}` ` ` `// Diagonally to the right up` ` ` `// (col increases and row` ` ` `// decreases)` ` ` `row = state[i] - 1, col = i + 1;` ` ` `while` `(col < N && row >= 0` ` ` `&& board[row][col] != 1) {` ` ` `col++;` ` ` `row--;` ` ` `}` ` ` `if` `(col < N && row >= 0` ` ` `&& board[row][col] == 1) {` ` ` `attacking++;` ` ` `}` ` ` `}` ` ` `// Return pairs.` ` ` `return` `(` `int` `)(attacking / 2);` `}` `// A utility function that` `// generates a board configuration` `// given the state.` `void` `generateBoard(` `int` `board[][N],` ` ` `int` `* state)` `{` ` ` `fill(board, 0);` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `board[state[i]][i] = 1;` ` ` `}` `}` `// A utility function that copies` `// contents of state2 to state1.` `void` `copyState(` `int` `* state1, ` `int` `* state2)` `{` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `state1[i] = state2[i];` ` ` `}` `}` `// This function gets the neighbour` `// of the current state having` `// the least objective value` `// amongst all neighbours as` `// well as the current state.` `void` `getNeighbour(` `int` `board[][N],` ` ` `int` `* state)` `{` ` ` `// Declaring and initializing the` ` ` `// optimal board and state with` ` ` `// the current board and the state` ` ` `// as the starting point.` ` ` `int` `opBoard[N][N];` ` ` `int` `opState[N];` ` ` `copyState(opState,` ` ` `state);` ` ` `generateBoard(opBoard,` ` ` `opState);` ` ` `// Initializing the optimal` ` ` `// objective value` ` ` `int` `opObjective` ` ` `= calculateObjective(opBoard,` ` ` `opState);` ` ` `// Declaring and initializing` ` ` `// the temporary board and` ` ` `// state for the purpose` ` ` `// of computation.` ` ` `int` `NeighbourBoard[N][N];` ` ` `int` `NeighbourState[N];` ` ` `copyState(NeighbourState,` ` ` `state);` ` ` `generateBoard(NeighbourBoard,` ` ` `NeighbourState);` ` ` `// Iterating through all` ` ` `// possible neighbours` ` ` `// of the board.` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `for` `(` `int` `j = 0; j < N; j++) {` ` ` `// Condition for skipping the` ` ` `// current state` ` ` `if` `(j != state[i]) {` ` ` `// Initializing temporary` ` ` `// neighbour with the` ` ` `// current neighbour.` ` ` `NeighbourState[i] = j;` ` ` `NeighbourBoard[NeighbourState[i]][i]` ` ` `= 1;` ` ` `NeighbourBoard[state[i]][i]` ` ` `= 0;` ` ` `// Calculating the objective` ` ` `// value of the neighbour.` ` ` `int` `temp` ` ` `= calculateObjective(` ` ` `NeighbourBoard,` ` ` `NeighbourState);` ` ` `// Comparing temporary and optimal` ` ` `// neighbour objectives and if` ` ` `// temporary is less than optimal` ` ` `// then updating accordingly.` ` ` `if` `(temp <= opObjective) {` ` ` `opObjective = temp;` ` ` `copyState(opState,` ` ` `NeighbourState);` ` ` `generateBoard(opBoard,` ` ` `opState);` ` ` `}` ` ` `// Going back to the original` ` ` `// configuration for the next` ` ` `// iteration.` ` ` `NeighbourBoard[NeighbourState[i]][i]` ` ` `= 0;` ` ` `NeighbourState[i] = state[i];` ` ` `NeighbourBoard[state[i]][i] = 1;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Copying the optimal board and` ` ` `// state thus found to the current` ` ` `// board and, state since c++ doesn't` ` ` `// allow returning multiple values.` ` ` `copyState(state, opState);` ` ` `fill(board, 0);` ` ` `generateBoard(board, state);` `}` `void` `hillClimbing(` `int` `board[][N],` ` ` `int` `* state)` `{` ` ` `// Declaring and initializing the` ` ` `// neighbour board and state with` ` ` `// the current board and the state` ` ` `// as the starting point.` ` ` `int` `neighbourBoard[N][N] = {};` ` ` `int` `neighbourState[N];` ` ` `copyState(neighbourState, state);` ` ` `generateBoard(neighbourBoard,` ` ` `neighbourState);` ` ` `do` `{` ` ` `// Copying the neighbour board and` ` ` `// state to the current board and` ` ` `// state, since a neighbour` ` ` `// becomes current after the jump.` ` ` `copyState(state, neighbourState);` ` ` `generateBoard(board, state);` ` ` `// Getting the optimal neighbour` ` ` `getNeighbour(neighbourBoard,` ` ` `neighbourState);` ` ` `if` `(compareStates(state,` ` ` `neighbourState)) {` ` ` `// If neighbour and current are` ` ` `// equal then no optimal neighbour` ` ` `// exists and therefore output the` ` ` `// result and break the loop.` ` ` `printBoard(board);` ` ` `break` `;` ` ` `}` ` ` `else` `if` `(calculateObjective(board,` ` ` `state)` ` ` `== calculateObjective(` ` ` `neighbourBoard,` ` ` `neighbourState)) {` ` ` `// If neighbour and current are` ` ` `// not equal but their objectives` ` ` `// are equal then we are either` ` ` `// approaching a shoulder or a` ` ` `// local optimum, in any case,` ` ` `// jump to a random neighbour` ` ` `// to escape it.` ` ` `// Random neighbour` ` ` `neighbourState[` `rand` `() % N]` ` ` `= ` `rand` `() % N;` ` ` `generateBoard(neighbourBoard,` ` ` `neighbourState);` ` ` `}` ` ` `} ` `while` `(` `true` `);` `}` `// Driver code` `int` `main()` `{` ` ` `int` `state[N] = {};` ` ` `int` `board[N][N] = {};` ` ` `// Getting a starting point by` ` ` `// randomly configuring the board` ` ` `configureRandomly(board, state);` ` ` `// Do hill climbing on the` ` ` `// board obtained` ` ` `hillClimbing(board, state);` ` ` `return` `0;` `}` |

**Output:**

0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0

**Complexity Analysis**

- The time complexity for this algorithm can be divided into three parts:
**Calculating Objective**– The calculation of objective involves iterating through all queens on board and checking the no. of attacking queens, which is done by our*calculateObjective*function in**O(N**time.^{2})

**Neighbour Selection and Number of neighbours**– The description of neighbours in our problem gives a total of**N(N-1)**neighbours for the current state. The selection procedure is*best fit*and therefore requires iterating through all neighbours, which is again**O(N**.^{2})

**Search Space**– Search space of our problem consists of a total of**N**^{N}^{ }states, corresponding to all possible configurations of the**N**Queens on board. Note that this is after taking into account the additional constraint of one queen per column.

- Therefore, the worst-case time complexity of our algorithm is
**O(N**. But, this worst-case occurs rarely in practice and thus we can safely consider it to be as good as any other algorithm there is for the N Queen problem. Hence, the effective time complexity consists of only calculating the objective for all neighbours up to a certain depth(no of jumps the search makes), which does not depend on^{N})**N.**Therefore, if the depth of search is**d**then the time complexity is**O(N**, which is^{2}* N^{2 }* d)**O(d*N**^{4}).