n_Queen_Problem

countN_Queen.java

/*
You are given an empty chess board of size N*N. Find the number of ways to place N queens on the board, such that no two queens can kill each other in one move. A queen can move vertically, horizontally and diagonally.

Input Format
A single integer N, denoting the size of chess board.

Constraints
1<=N<=11

Output Format
A single integer denoting the count of solutions.

Sample Input
4
Sample Output
2
 */

package Second_Assignment;

import  java.util.*;

public class countN_Queen {
    public static void main(String[] args) {


        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();

        int[][] board = new int[n][n];

        //1.print count and all combination easy methode

        int count = nQueenCombi(board,0,n);
        System.out.println(count);


        System.out.println();
        System.out.println();



        //2.Store all the combination inside a only single List...

        System.out.println("by only single List");
        ArrayList<String> al = nQueenCombibySingleArrayList(board,0,n);
        for (int i = 0; i < al.size(); i=i+4) {
            for (int j = i; j <i+4 ; j++) {
                System.out.print(al.get(j)+" ");

            }
            System.out.println();

        }
        System.out.println(al);


        System.out.println();
        System.out.println();



        //3. Store the all combination iList inside a List  like List<list<String>> ....


        System.out.println("By list inside list");

        char[][] board2 = new char[n][n];
        for(char[] ch :board2) {
            Arrays.fill(ch, '.');
        }

        List<List<String>> alal= nQueenCombibyDoubleArrayList(board2,0,n);

        System.out.println("double list");

        try {


            for (int i = 0; i < alal.size(); i++) {
                for (int j = 0; j < alal.get(i).size(); j++) {
                    System.out.println(alal.get(j));

                }
                System.out.println();


            }
        }
        catch (Exception e)
        {
            System.out.println(e);
        }
        System.out.println(alal);



    }



    //1.1This methode print the all combination of n queen problem and also how many combination is possible for give  n value.....


    static int nQueenCombi(int[][] board , int row , int n)
    {
        if(row == n)
        {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(board[i][j] == 1)
                        System.out.print("Q"+" " );
                    else
                        System.out.print("-"+" ");

                }
                System.out.println();
            }
            System.out.println("*******************************");
            return 1;
        }

        int length = 0;
        for(int col = 0;col<n;col++)
        {
            if(kyaQueenRakkhu(board,row,col,n))
            {
                board[row][col] = 1;
                length+=nQueenCombi(board,row+1,n);
                board[row][col] = 0;
            }
        }
        return length;
    }




    // 2.1this n Quenn methode for store the queen output inside the Only List........


    static ArrayList<String> nQueenCombibySingleArrayList(int[][] board , int row , int n)
    {
        if(row == n)
        {
            ArrayList<String> al = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(board[i][j] == 1)
                        al.add("Q");
                    else
                        al.add("_");

                }

            }
//            System.out.println("*******************************");
            return al;
        }

        ArrayList<String> al = new ArrayList<>();
        for(int col = 0;col<n;col++)
        {
            if(kyaQueenRakkhu(board,row,col,n))
            {
                board[row][col] = 1;
                ArrayList<String> al2 = nQueenCombibySingleArrayList(board,row+1,n);
                for (int i = 0; i < al2.size(); i++) {
                    al.add(al2.get(i));
                }
                board[row][col] = 0;
            }
        }
        return al;
    }




    // 1.2&& 2.2This methode is for check quenn is safe or not to place ........ work on List<String> and int type or also void

    static boolean kyaQueenRakkhu(int[][] board,int row,int col ,int n)
    {
        for (int cr=0;cr<row;cr++)
        {
            if (board[cr][col] == 1)
                return false;
        }

        int cr = row;
        int cc = col;

        while (cr>=0 && cc>=0)
        {
            if(board[cr][cc] ==1)
                return false;
            cr--;
            cc--;
        }

        cr = row;
        cc= col;

        while (cr>=0 && cc<n)
        {
            if(board[cr][cc] == 1)
                return false;
            cr--;
            cc++;
        }
        return true;


    }








//    leetCode Question of N queen ....



    //3.1List inside List

    static List<List<String>> nQueenCombibyDoubleArrayList(char[][] board , int row , int n)
    {
        List<List<String>> outer = new ArrayList<List<String>>();
        if(row == n)
        {
            List<String> inner = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                inner.add(String.valueOf(board[i]));
            }
            outer.add(inner);

            return outer;
        }

        ArrayList<String> al = new ArrayList<>();
        for(int col = 0;col<n;col++)
        {
            if(kyaQueenRakkhu1(board,row,col,n))
            {
                board[row][col] = 'Q';
                outer.addAll(nQueenCombibyDoubleArrayList(board,row+1,n));

                board[row][col] = '.';
            }
        }
        return outer;
    }





    // 3.2This method for check char type board path of List inside List type  List<List<String> ....
    static boolean kyaQueenRakkhu1(char[][] board,int row,int col ,int n)
    {
        for (int cr=0;cr<row;cr++)
        {
            if (board[cr][col] == 'Q')
                return false;
        }

        int cr = row;
        int cc = col;

        while (cr>=0 && cc>=0)
        {
            if(board[cr][cc] =='Q')
                return false;
            cr--;
            cc--;
        }

        cr = row;
        cc= col;

        while (cr>=0 && cc<n)
        {
            if(board[cr][cc] == 'Q')
                return false;
            cr--;
            cc++;
        }
        return true;


    }
}







//Output

/*
4
- Q - -
- - - Q
Q - - -
- - Q -
*******************************
- - Q -
Q - - -
- - - Q
- Q - -
*******************************
2


by only single List
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
_ _ Q _
Q _ _ _
_ _ _ Q
_ Q _ _
[_, Q, _, _, _, _, _, Q, Q, _, _, _, _, _, Q, _, _, _, Q, _, Q, _, _, _, _, _, _, Q, _, Q, _, _]


By list inside list
double list
[.Q.., ...Q, Q..., ..Q.]
[..Q., Q..., ...Q, .Q..]
java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
[[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]


 */