# N Queens Puzzle.

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

Let us first understand what we want to achieve? what is the input and what will be the expected output?

You are given a chess board of N * N size, you have to place N Queens in chess board in such a way that no queens are attacking each other.

Sample Input and output for 4 * 4 chess board

Remember, Queens attacks on same row, on same column as well as diagonally.

### Algorithm

We will use Backtracking algorithm approach for placing N Queens on N*N chess board.

1.  Since Queens attack on same rows, only one Queen per row can be set.
2.  Since Queens attack on same column, only one Queen per column can be set.
3.  We can start placing Queens either column wise that is one column at a time or can start placing
Queens row wise that is one row at a time.
We will be using Row wise placement. Start from Row 0, check the safe position to place on
Row 0 and place a queen on row 0. once queen is placed on Row 0, move to Row 1 and so on.
4.  Before placing a queen on any position in a row, we first check is there any other already
placed queens on prior rows attacking on this position.
if no already placed queen is attacking, then only place a queen on position.

5.  So when we are working on say Row 2. and we are looking for safe position on Row 2,
then we need to check the safe position on Row 2 against Row 1 and Row 0 as that are the rows

where we already placed a Queens.
6.  If queen placement is not leading to a solution, then backtrack and change the position of already
placed queen and retry.

### Java Program to place N Queens on N*N Chess board.

```package backtracking;

public class NQueens2DArray {
public static void main(String[] args) {
placeQueens(4); // Lets take example of 4*4
}

private static void placeQueens(int gridSize){

//If Grid is 1*1 or 2*2 or 3*3 then solution is not possible as,
//In 1*1 or 2*2 grid, Queen placed in 1st row at any position will attack queen placed at all the positions in row 2.
//In 3*3 grid, Queen placed in 1st row and 2nd row for all combinations position will attack queen placed at all the positions in row 3.
if(gridSize<4){
System.out.println("No Solution available");
}else{
int[][] board = new int[gridSize][gridSize];
placeAllQueens(board, 0);
printBoard(board);
}
}
private static boolean placeAllQueens(int board[][], int row){
if(row>=board.length){
return true;
}

boolean isAllQueensPlaced = false;
for (int j = 0; j < board.length; j++) {

if(isSafe(board, row, j)){
board[row][j] = 1;
isAllQueensPlaced = placeAllQueens(board, row+1);
}
if(isAllQueensPlaced){
break;
}else{
board[row][j] = 0;
}
}
return isAllQueensPlaced;
}

private static boolean isSafe(int board[][], int row, int col){

//Check Left Upper Diagonal
for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
if(board[i][j] == 1){
return false;
}
}

//Check Right Upper Diagonal
for (int i = row-1, j = col+1; i >= 0 && j < board.length; i--, j++) {
if(board[i][j] == 1){
return false;
}
}

//Check in same Column
for (int i = row-1; i >= 0; i--) {
if(board[i][col] == 1){
return false;
}
}

return true;
}

private static void printBoard(int[][] board){
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board.length; col++) {
if(board[row][col] == 1){
System.out.print("Q ");
}else{
System.out.print("_ ");
}
}
System.out.println();
}
System.out.println("");
}

}

```

Output:
_    Q   _    _
_    _    _    Q
Q    _    _    _
_    _    Q   _

### You may also like to see

#### N Queens Puzzle Optimized using 1D array.

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.