Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
3.7 kB
2
Indexable
Never
import java.util.*;

public class NQueens {

    String nQueens(int n) {
        List<String> ways = new ArrayList<>();
        boolean[][] chess = new boolean[n][n];
        solveNQueen(chess,0,n,ways);
        String waysString = "";
        if(ways.size()>0){
            for(int i=0; i< ways.size();i++){
                waysString+=ways.get(i);
            }
            return waysString;
        }
        return "No Solution Exists";
    }

    void solveNQueen(boolean[][] chess, int row, int n, List<String> ways){
        if(row == n){
            addOutPut(chess,n,ways);
            return;
        }
        for(int col=0;col<n;col++){
            if(isQueenSafe(chess,row,col,n)==true){
                chess[row][col] = true;
                solveNQueen(chess,row+1,n, ways);
                chess[row][col] = false;
            }
        }
    }

    boolean isQueenSafe(boolean[][] chess, int row, int col, int n){

        for( int r = row ; r >= 0 ; r-- ){
            if(chess[r][col] == true) return false;
        }

        for( int r = row, c = col ; r >= 0 && c >= 0 ; r--,c-- ){
            if(chess[r][c] == true) return false;
        }

        for( int r = row, c = col ; r >= 0 && c < n ;r--,c++ ){
            if(chess[r][c] == true) return false;
        }

        return true;
    }

    void addOutPut(boolean[][] chess,int n,List<String> ways){

        String output = "";
        for(int row = 0;row<n;row++){
            String str = "";
            for(int col=0;col<n;col++){
                if(chess[row][col]==true){
                    str+='1';
                }else{
                    str+='0';
                }
            }
            output += str + "\n";
        }
        ways.add(output);

    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =  scanner.nextInt();
        scanner.close();
        NQueens result = new NQueens();
        String board = result.nQueens(n);
        System.out.println(board);
    }
}
/* 
Crio Methodology

Milestone 1: Understand the problem clearly
1. Ask questions & clarify the problem statement clearly.
2. Take an example or two to confirm your understanding of the input/output

Milestone 2: Finalize approach & execution plan
1. Understand what type of problem you are solving and see if you can recollect solving similar problems in the past
      a. Obvious logic (this would only test ability to convert logic to code)
      b. Figuring out logic
      c. Knowledge of specific algorithm, data structure or pattern
      d. Knowledge of specific domain or concepts
      e. Mapping real world into abstract concepts/data structures
2. Brainstorm multiple ways to solve the problem and pick one based on the TC/SC requirements
3. Get to a point where you can explain your approach to a 10 year old

Milestone 3 : Come up with an Instruction Manual for a 10 year old
1. Take a stab at the high-level logic & write it down like a detailed Instruction Manual for a 10 Year old where each line of the manual can be expanded into a logical line(s) of code.
2. Try to offload logic out of the main section as much as possible by delegating to functions.

Milestone 4: Code by expanding your 10 Year Olds "Instruction Manual
1. Run your code snippets at every logical step to test correctness (Helps avoid debugging larger pieces of code later)
2. Make sure you name the variables, functions clearly.
3. Use libraries as much as possible

Milestone 5: Prove that your code works using custom test cases
1. Make sure you check bo
Leave a Comment