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+='.';
                }
            }
            list.add(ans);
        }
        allBoards.add(list);
    }
    
    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;
    }
}

Leave a Comment