forked from avinashbest/java-coding-ninjas
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNQueens.java
More file actions
112 lines (99 loc) · 3.38 KB
/
Copy pathNQueens.java
File metadata and controls
112 lines (99 loc) · 3.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
package backtracking;
import java.util.Scanner;
/*You are given N, and for a given N x N chessboard, find a way to place N queens such that no queen can attack any other queen on the chess board.
A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the other queens.
You have to print all such configurations.
Input Format :
Line 1 : Integer N
Output Format :
One Line for every board configuration.
Every line will have N*N board elements printed row wise and are separated by space
Note : Don't print anything if there isn't any valid configuration.
Constraints :
1<=N<=10
Sample Input 1:
4
Sample Output 1 :
0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 */
public class NQueens {
public static void placeNQueens(int N) {
int[][] board = new int[N][N];
placeQueens(board, 0, N);
}
private static void placeQueens(int[][] board, int row, int N) {
// valid board configuration
if (N == row) {
print2dArray(board);
System.out.println();
}
// check for all columns
for (int j = 0; j < N; j++) {
// check if it is safe to place Queen
if (isBoardSafe(board, row, j)) {
board[row][j] = 1;
// if it is safe -> then place the queen & move to next row
placeQueens(board, row + 1, N);
board[row][j] = 0;
}
}
}
private static boolean isBoardSafe(int[][] board, int row, int column) {
int N = board.length;
for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row + 1, j = column + 1; i < N && j < N; i++, j++) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row - 1, j = column + 1; i >= 0 && j < N; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row + 1, j = column - 1; i < N && j >= 0; i++, j--) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row - 1; i >= 0; i--) {
if (board[i][column] == 1) {
return false;
}
}
for (int i = row + 1; i < N; i++) {
if (board[i][column] == 1) {
return false;
}
}
return true;
}
public static void print2dArray(int[][] arr) {
System.out.println("Possible Placing of the Queens:");
System.out.println("-----------------");
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i][j] != 0)
System.out.print("👑" + "\t");
else
System.out.print("❌" + "\t");
}
System.out.println();
}
System.out.println("-----------------");
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("Enter the size of the board: ");
int size = scan.nextInt();
if (size > 3) {
placeNQueens(size);
} else {
System.out.println("Size is less than 4! No placement of Queen is possible :(");
}
}
}