Question

Implement the N-Queens algorithm using backtracking to place 8 queens on a 8x8 chess board in a way that no two queens can attack each other. Your output should print out a 8x8 grid of cells with a "1" to indicate a queen placement.

JAVA CODE

Answer 1

public class Queens8 {

public static boolean safe(int[] mat, int n) {
for (int i = 0; i < n; i++) {
if (mat[i] == mat[n])
return false;
if ((mat[i] - mat[n]) == (n - i))
return false;   
if ((mat[n] - mat[i]) == (n - i))
return false;
}
return true;
}

//this function prints the queens
public static void print(int[] mat) {
int n = mat.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i] == j)
System.out.print("1 ");
  
else
System.out.print("0 ");
}
System.out.println();
}
System.out.println();
}

//this function does the backtracking and all the possible permutations are tried
public static void solution(int n) {
int[] arr = new int[n];
solution(arr, 0);
}

public static void solution(int[] mat, int k) {
int n = mat.length;
if (k == n)
print(mat);
else {
for (int i = 0; i < n; i++) {
mat[k] = i;
if (safe(mat, k))
solution(mat, k+1);
}
}
}

public static void main(String[] args) {
int n = 8;
solution(n);
}

}