# N-Queens Solved

``````import java.util.*;
class Main {
public static void main(String[] args) {
int n=4;
int[][] chess = new int[n][n];
NQueens(chess, 0);
}
public static void NQueens(int[][] chess, int row) {
if(row == chess.length) {
display(chess);
System.out.println();
return;
}
for(int col=0; col<chess.length; col++) {
if(isSafe(chess, row, col)) {
chess[row][col] = 1;
NQueens(chess, row+1);
chess[row][col] = 0;
}
}
}
public static void display(int[][] chess) {
for(int row=0; row<chess.length;row++) {
for(int col=0; col<chess.length; col++) {
// System.out.print(chess[row][col]);
if(chess[row][col]==1) {
System.out.print("Q ");
}
else {
System.out.print("- ");
}
}
System.out.println();
}
}
public static boolean isSafe(int[][] chess, int row, int col) {
//vertical check
for(int i=row-1, j=col; i>=0; i--) {
if(chess[i][j] == 1) {
return false;
}
}
//left diagonal check
for(int i=row-1, j=col-1; i>=0&&j>=0; i--, j--) {
if(chess[i][j] == 1) {
return false;
}
}
//right diagonal check
for(int i=row-1, j=col+1; i>=0&&j<chess.length; i--, j++) {
if(chess[i][j] == 1) {
return false;
}
}
return true;
}
}``````

## N-Queens (LeetCode)

``````class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> allBoards = new ArrayList<>();
int[][] chess = new int[n][n];
NQueens(chess, allBoards, 0);
return allBoards;
}

public static void NQueens(int[][] chess, List<List<String>> allBoards, int row) {
if(row == chess.length) {
save(chess, allBoards);
System.out.println();
return;
}
for(int col=0; col<chess.length; col++) {
if(isSafe(chess, row, col)) {
chess[row][col] = 1;
NQueens(chess, allBoards, row+1);
chess[row][col] = 0;
}
}
}

public static void save(int[][] chess, List<List<String>> allBoards) {
List<String> list = new ArrayList<String>();
for(int row=0; row<chess.length;row++) {
String ans="";
for(int col=0; col<chess.length; col++) {
if(chess[row][col]==1) {
ans+='Q';
}
else {
ans+='.';
}
}
}
}

public static boolean isSafe(int[][] chess, int row, int col) {
//vertical check
for(int i=row-1, j=col; i>=0; i--) {
if(chess[i][j] == 1) {
return false;
}
}
//left diagonal check
for(int i=row-1, j=col-1; i>=0&&j>=0; i--, j--) {
if(chess[i][j] == 1) {
return false;
}
}
//right diagonal check
for(int i=row-1, j=col+1; i>=0&&j<chess.length; i--, j++) {
if(chess[i][j] == 1) {
return false;
}
}
return true;
}
}``````

Categories DSA