N Queen (Second Try)

 avatar
user_4666436
java
2 years ago
2.3 kB
2
Indexable
Never
package recursion;

//https://pepcoding.com/resources/online-java-foundation/recursion-backtracking/n-queens-official/ojquestion

import java.util.*;

public class NQueensOfRecursionBackTracking {
	
	public static void main(String args[]) {
		
		Scanner scn = new Scanner(System.in);
		
		int numOfQueen = scn.nextInt();
		
		int[][] arr = new int[numOfQueen][numOfQueen];
		
		printNQueens(arr, "", 0);
	}
	
	public static void printNQueens(int[][] chess, String qsf, int row) {
		
		if(row == chess.length) {
			System.out.println(qsf+".");
			return;
		}
		
		int cou = 1;
		for(int j=0;j<chess[0].length;j++) {
			if(chess[row][j] == 0) {
				cou = 2;
				chess[row][j] = 2;
				chess = markEligibleMoves(chess, j, row+1);
				printNQueens(chess, qsf+row+"-"+j+", ", row+1);
				chess[row][j] = 0;
				chess = omitPreviousMoves(chess, j, row+1);
			}
		}
		if(cou == 1) {
			return;
		}
        
    }
	
	public static int[][] omitPreviousMoves(int[][] arr, int j, int row) {
		if(row == 0) {
			return arr;
		}
		int start = j;
		int end = row;
		
		//for left diagonal move
		if(start != 0 && end != arr.length) {
			while(start-1 >= 0 && end != arr.length) {
				start -= 1;
				arr[end][start] -= 1;
				end += 1;
			}
		}
		
		//for vertical move
		start = row;
		end = j;
		while(start != arr.length) {
			arr[start][end] -= 1;
			start += 1;
		}
		
		//for right diagonal move
		start = row;
		end = j;
		if(start != arr.length) {
			while(start != arr.length && end+1 != arr.length) {
				end += 1;
				arr[start][end] -= 1;
				start += 1;
			}
		}
		
		return arr;
	}
	
	public static int[][] markEligibleMoves(int[][] arr, int j, int row) {
		if(row == 0) {
			return arr;
		}
		int start = j;
		int end = row;
		
		//for left diagonal move
		if(start != 0 && end != arr.length) {
			while(start-1 >= 0 && end != arr.length) {
				start -= 1;
				arr[end][start] += 1;
				end += 1;
			}
		}
		
		//for vertical move
		start = row;
		end = j;
		while(start != arr.length) {
			arr[start][end] += 1;
			start += 1;
		}
		
		//for right diagonal move
		start = row;
		end = j;
		if(start != arr.length) {
			while(start != arr.length && end+1 != arr.length) {
				end += 1;
				arr[start][end] += 1;
				start += 1;
			}
		}
		
		return arr;
	}

}