# N Queen (Second Try)

user_4666436
java
2 years ago
2.3 kB
2
Indexable
Never
```package recursion;

//https://pepcoding.com/resources/online-java-foundation/recursion-backtracking/n-queens-official/ojquestion

import java.util.*;

public class NQueensOfRecursionBackTracking {

public static void main(String args[]) {

Scanner scn = new Scanner(System.in);

int numOfQueen = scn.nextInt();

int[][] arr = new int[numOfQueen][numOfQueen];

printNQueens(arr, "", 0);
}

public static void printNQueens(int[][] chess, String qsf, int row) {

if(row == chess.length) {
System.out.println(qsf+".");
return;
}

int cou = 1;
for(int j=0;j<chess[0].length;j++) {
if(chess[row][j] == 0) {
cou = 2;
chess[row][j] = 2;
chess = markEligibleMoves(chess, j, row+1);
printNQueens(chess, qsf+row+"-"+j+", ", row+1);
chess[row][j] = 0;
chess = omitPreviousMoves(chess, j, row+1);
}
}
if(cou == 1) {
return;
}

}

public static int[][] omitPreviousMoves(int[][] arr, int j, int row) {
if(row == 0) {
return arr;
}
int start = j;
int end = row;

//for left diagonal move
if(start != 0 && end != arr.length) {
while(start-1 >= 0 && end != arr.length) {
start -= 1;
arr[end][start] -= 1;
end += 1;
}
}

//for vertical move
start = row;
end = j;
while(start != arr.length) {
arr[start][end] -= 1;
start += 1;
}

//for right diagonal move
start = row;
end = j;
if(start != arr.length) {
while(start != arr.length && end+1 != arr.length) {
end += 1;
arr[start][end] -= 1;
start += 1;
}
}

return arr;
}

public static int[][] markEligibleMoves(int[][] arr, int j, int row) {
if(row == 0) {
return arr;
}
int start = j;
int end = row;

//for left diagonal move
if(start != 0 && end != arr.length) {
while(start-1 >= 0 && end != arr.length) {
start -= 1;
arr[end][start] += 1;
end += 1;
}
}

//for vertical move
start = row;
end = j;
while(start != arr.length) {
arr[start][end] += 1;
start += 1;
}

//for right diagonal move
start = row;
end = j;
if(start != arr.length) {
while(start != arr.length && end+1 != arr.length) {
end += 1;
arr[start][end] += 1;
start += 1;
}
}

return arr;
}

}```