-
Notifications
You must be signed in to change notification settings - Fork 0
/
NQueen.java
79 lines (68 loc) · 2.24 KB
/
NQueen.java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class NQueen {
private static int N;
private static boolean col[];
private static boolean diagonal1[];
private static boolean diagonal2[];
private static LinkedList<Point> points;
static class Point {
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static boolean nQueenHelper(int n) {
return nQueen(n, 0);
}
public static boolean nQueen(int n, int depth) {
if (depth == n) {
return true;
}
// Back Tracking
for (int i = 0; i < n; i++) {
if (!col[i] && !diagonal1[depth - i + n-1] && !diagonal2[depth + i]) {
col[i] = true;
diagonal1[depth - i + n-1] = true;
diagonal2[depth+i] = true;
points.add(new Point(depth, i));
boolean truth = nQueen(n, depth+1);
if (truth)
return true;
col[i] = false;
diagonal1[depth - i + n-1] = false;
diagonal2[depth+i] = false;
points.remove();
}
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please enter the number N : ");
N = Integer.parseInt(br.readLine());
col = new boolean[N];
diagonal1 = new boolean[N*2-1];
diagonal2 = new boolean[N*2-1];
points = new LinkedList<>();
//Output:
// N Queen exist on 4 x 4 Matrix
// points:
// 0 1
// 1 3
// 2 0
// 3 2
if (nQueenHelper(N)) {
System.out.println("\n" + "N Queen Exist on " + N + " x " + N + " Matrix" + "\n");
System.out.println("points:");
for (Point point : points)
System.out.println(point.x + ", " + point.y);
} else {
System.out.println("N Queen doesn't exist on " + N + " x " + N + " Matrix" + "\n");
}
}
}