The input of the problem is the N size of the board and the output its solution.
This is a nontrivial problem and there are many approaches to solve it such as constraint programming, logic programming or genetic algorithms.
The solution range is N^2*N so a brute force algorithm would take much time to solve it. For instance, in the N=3 case there would be (3*3)^3=387420489 possible placements.
I made a depth-first search (DFS) and backtracking (BT) algorithm to solve it.
In my proposed solution, the root of the tree represents the empty board and each node of the tree represents a different board configuration. On the other hand, the algorithm explores the branches of the tree (using DFS) that have a promising solution (BT), otherwise the branch is pruned and another one is explored.
In the following tree an example of the algorithm for N=4 is shown:
I implemented the algorithm in Java, for values of N larger than 14 you might need to increase the size of the java stack by adding -Xss8m in the java options as for these values there is a very deep recursion and it could be overflowed. The code is shown below:
/**
* N-Queens Problem: Using Depth-First Search & Backtracking
* @author gru
*/
public class Main {
public static void NQueen(int N, int[][] board, int i, int j, boolean found) {
//if found we return the result
if (!found) {
//check if the current position is valid
if (IsValid(board, i, j)) {
board[i][j] = 1;
//Uncomment to track the partial results
//System.out.println("[+]New Queen added at (" + i + "," + j + ")");
//PrintBoard(board);
//check if this was the last queen
if (i == N - 1) {
found = true;
PrintBoard(board);
}
//call the next iteration
NQueen(N, board, i + 1, 0, found);
} else {
//if the position is not valid
//if it was the last row we do backtracking
while (j >= N - 1) {
int[] a = BackTracking(board, i, j);
i = a[0];
j = a[1];
//Uncomment to track the partial results
//System.out.println("[+]Rolled back at (" + i + "," + j + ")");
//PrintBoard(board);
}
//we do the next call
NQueen(N, board, i, j + 1, false);
}
}
}
public static int[] BackTracking(int[][] board, int i, int j) {
int[] a = new int[2];
for (int x = i; x >= 0; x--) {
for (int y = j; y >= 0; y--) {
//seeks the last queen
if (board[x][y] != 0) {
//deletes the last queen and returns the position
board[x][y] = 0;
a[0] = x;
a[1] = y;
return a;
}
}
}
return a;
}
public static boolean IsValid(int[][] board, int i, int j) {
int x;
//check if there is any queen in the same column
for (x = 0; x < board.length; x++) {
if (board[i][x] != 0) {
return false;
}
}
//check if there is any queen in the same row
for (x = 0; x < board.length; x++) {
if (board[x][j] != 0) {
return false;
}
}
//check if there is any queen in the diagonals
if (!IsSafeDiag(board, i, j)) {
return false;
}
return true;
}
public static boolean IsSafeDiag(int[][] board, int i, int j) {
int ii = i;
int jj = j;
while (jj >= 0 && ii >= 0 && ii < board.length && jj < board.length) {
if (board[ii][jj] != 0) {
return false;
}
jj++;
ii++;
}
ii = i;
jj = j;
while (jj >= 0 && ii >= 0 && ii < board.length && jj < board.length) {
if (board[ii][jj] != 0) {
return false;
}
jj--;
ii--;
}
ii = i;
jj = j;
while (jj >= 0 && ii >= 0 && ii < board.length && jj < board.length) {
if (board[ii][jj] != 0) {
return false;
}
jj--;
ii++;
}
ii = i;
jj = j;
while (jj >= 0 && ii >= 0 && ii < board.length && jj < board.length) {
if (board[ii][jj] != 0) {
return false;
}
jj++;
ii--;
}
return true;
}
public static void PrintBoard(int[][] board) {
System.out.print(" ");
for (int j = 0; j < board.length; j++) {
System.out.print(j);
}
System.out.print("\n");
for (int i = 0; i < board.length; i++) {
System.out.print(i);
for (int j = 0; j < board.length; j++) {
if (board[i][j] == 0) {
System.out.print(" ");
} else {
System.out.print("Q");
}
}
System.out.print("\n");
}
}
public static void main(String[] args) {
//we parse the input, which is the size of the problem
int N = Integer.parseInt(args[0]);
//we create a board
int[][] board = new int[N][N];
//we call the method that solves the problem
NQueen(N, board, 0, 0, false);
}
}
