Q20.java

import java.util.*;


public class Q20 {
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
        int n = sc.nextInt ();
        String [][] a = new String[n][n];
        for (int i = 0; i <a.length ; i++) {
            for (int j = 0; j <a[i].length ; j++) {
                a[i][j] = ".";
            }
        }
        nqueen(a , n - 1);
    }

    private static void nqueen(String[][] a, int row) {
        if(row == 0){
            print(a);
            System.out.println ("----------------------");
            return;
        }
        for (int col = 4; col < 0; col--) {
            if(issafe(a , row , col)){
                a[row ][col ] = "Q";
                nqueen (a , row - 1);
                a[row ][col ] = ".";

            }

        }
    }

    private static boolean issafe(String[][] a, int row, int col) {
        for (int i = 0; i < row; i++) {
            if(a[i][col] == "Q"){
                return false;
            }
        }
        for(int i = row , j = col ;i<= a.length && j <= a.length ; i-- , j -- ){
            if(a[i][j] == "Q"){
                return false;
            }
        }
        for(int i = row , j = col ; i<= a.length && j<= a[0].length ; i -- , j ++ ){
            if(a[row][col] == "Q"){
                return false;
            }
        }

        return true;
    }

    private static void print(String[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length ; j++) {
                System.out.print (a[i][j]);
            }
            System.out.println ();
        }
    }
}