**Objective : **In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move.(Source: http://www.math.utah.edu/~alfeld/queens/queens.html)

Here we are solving it for N queens in NxN chess board.

Approach:

This earlier approach we have seen solution matrix, at every row we have only one entry as 1 and rest of the entries are 0. Solution matrix takes O(N^{2}) space. We can reduce it to O(N). We will solve it by taking one dimensional array and consider solution[1] = 2 as “Queen at 1st row is placed at 2nd column.

*result[i]=j means queen at i-th row is placed at j-th column.*

Check if Queens placed at (x1, y1) and (x2,y2) are safe

- x1==x2 means same rows,
- y1==y2 means same columns
- |x2-x1|==|y2-y1| means they are placed in diagonals.

**Code:**

import java.util.Arrays; | |

public class NQueens { | |

static int[] result; // this array will store the result | |

// result[i]=j; means queen at i-th row is placed at j-th column. | |

// Queens placed at (x1, y1) and (x2,y2) | |

// x1==x2 means same rows, y1==y2 means same columns, |x2-x1|==|y2-y1| means | |

// they are placed in diagonals. | |

public boolean canPlace(int x2, int y2) { | |

// This function will check if queen can be placed (x2,y2), or we can | |

// say that Can queen at x2 row is placed at y2 column. | |

// for finding the column for x2 row, we will check all the columns for | |

// all the rows till x2-1. | |

for (int i = 0; i < x2; i++) { | |

//result[i] == y2 => columns are same | |

//|i – x2| == |result[i] – y2| => in diagonals. | |

if ((result[i] == y2) | |

|| (Math.abs(i – x2) == Math.abs(result[i] – y2))) { | |

return false; | |

} | |

} | |

return true; | |

} | |

public void placeQueens(int x, int size) { | |

for (int i = 0; i < size; i++) { | |

//check if queen at xth row can be placed at i-th column. | |

if (canPlace(x, i)) { | |

result[x] = i; // place the queen at this position. | |

if (x == size – 1) { | |

System.out.println("Order of " + size + " queens" | |

+ Arrays.toString(result)); | |

} | |

placeQueens(x + 1, size); | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int n = 6; | |

result = new int[n]; | |

NQueens i = new NQueens(); | |

i.placeQueens(0, n); | |

} | |

} |

Output: Order of 6 queens[1, 3, 5, 0, 2, 4] Order of 6 queens[2, 5, 1, 4, 0, 3] Order of 6 queens[3, 0, 4, 1, 5, 2] Order of 6 queens[4, 2, 0, 5, 3, 1]

**Reference** :”https://www.youtube.com/watch?v=p4_QnaTIxkQ”