Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings
This repository was archived by the owner on Oct 29, 2020. It is now read-only.

Latest commit

 

History

History
History
90 lines (90 loc) · 2.1 KB
/

NQueens.java

File metadata and controls

90 lines (90 loc) · 2.1 KB
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
public class NQueens {
public class Board {
public int[][] solution;
public int length;
public Board(int N) {
solution = new int[N][N];
length = N;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
solution[i][j] = 0;
}
}
}
private boolean canPlaceRow(int row, int column) {
for (int i = 0; i < column; i++) {
if (solution[row][i] == 1) {
return false;
}
}
return true;
}
private boolean canPlaceColumn(int row, int column) {
for (int i = 0; i < row; i++) {
if (solution[i][column] == 1) {
return false;
}
}
return true;
}
private boolean canPlaceDiagonal(int row, int column) {
for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) {
if (solution[i][j] == 1) {
return false;
}
}
for (int i = row, j = column; i < length && j >= 0; i++, j--) {
if (solution[i][j] == 1) {
return false;
}
}
return true;
}
public boolean canPlaceRowColumn(int row, int column) {
return (canPlaceRow(row, column) && canPlaceDiagonal(row, column) &&
canPlaceColumn(row, column));
}
public void printSol() {
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
System.out.print(" " + solution[i][j]);
}
System.out.println();
}
System.out.println();
}
}
public Board sol;
private int numSol;
public NQueens(int N) {
sol = new Board(N);
numSol = 0;
}
public void solve(int N) {
placeQueens(0, N);
System.out.print("A total of " + numSol + " solutions.\n");
}
private boolean placeQueens(int queen, int N) {
if (queen == N) {
sol.printSol();
++numSol;
return false;
}
for (int row = 0; row < N; row++) {
if (sol.canPlaceRowColumn(row, queen)) {
sol.solution[row][queen] = 1;
if (placeQueens(queen + 1, N)) {
return true;
}
sol.solution[row][queen] = 0;
}
}
return false;
}
public static void main(String[] args) {
System.out.print("Enter the length of side of chessboard:\n");
int N = Integer.parseInt(System.console().readLine());
NQueens q = new NQueens(N);
q.solve(N);
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.