8 queens problem in java without using backtracking
8 queens problem in java without using backtracking
n Queens non-attacking problem is a famous problem in chess where n queens are placed on a chessboard in such a way that no queen is going to attack one another. The size of a chessboard is 88 and as a result, the maximum number of queens that can be placed in a chessboard so that all queens are non-attacking is 8. This is a backtracking problem and without backtracking brute force method is considered.
enumeration() method is used for obtaining the value "Q" only one at a time along the horizontal and vertical lines.
The complete Java code for the above problem:
public class Main {
public static void printQueens(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i] == j)
System.out.print("Q ");
else
System.out.print("- ");
}
System.out.println();
}
System.out.println();
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void enumerate(int[] a, boolean[] d1, boolean[] d2, int k) {
int n = a.length;
if (k == 0) {
printQueens(a);
}
for (int i = 0; i < k; i++) {
swap(a, i, k-1);
int j = k-1;
if (!d1[j + a[j]] && !d2[n + j - a[j]]) {
d1[j + a[j]] = true;
d2[n + j - a[j]] = true;
enumerate(a, d1, d2, k-1);
d1[j + a[j]] = false;
d2[n + j - a[j]] = false;
}
swap(a, i, k-1);
}
}
public static void main(String[] args) {
int n =8;
int a[] = new int[8];
boolean[] d1 = new boolean[2*8];
boolean[] d2 = new boolean[2*8];
for (int i = 0; i < 8; i++)
a[i] = i;
enumerate(a, d1, d2, 8);
}
}
Step by step
Solved in 3 steps with 2 images
