## Friday, September 9, 2011

### N-Queens Problem

The N-Queens problem consists in placing N queens in a NxN cheese board, so that none of them attack each other, as we show in the following figure:

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;
j = a;
//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;
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 = x;
a = 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);

//we create a board
int[][] board = new int[N][N];

//we call the method that solves the problem
NQueen(N, board, 0, 0, false);
}
}
```

1. my improved version for values of N = 35 executed in 3min 58 sec

/*
* Elimination of recursion.
* Data structure used is the table, cause we need to represent a single data ( column index ) in each row
*/

package deptfirstsearch;

import java.util.Scanner;
/**
*
* @author hangouby@gmail.com
*/
public class DeptFirstSearch {

//Method that solve our problem
private static long NQueen(int n, int[] board, int i, boolean correct, long failure) {
board[i] = 1;
//if the solution found (true), return the result
while (!correct) {
//Add a new queen if the current position is valid
if (IsValid(board, i)) {
//check if this was the last queen
if (i == n - 1)
return failure;
//call the next iteration
i++;
board[i] = 1;
}else { //position is not valid
//seeks the last queen and remove it
while (board[i] == n) {
failure++;
i--;
} //we do the next call
board[i]++;
correct = false;

}
}
return failure;
}
/*
//method that remove the last queen and return it position
private static int[] SeekLastQueen(int[][] board, int i, int j) {
int[] a = new int;
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 = x;
a = y;
return a;
}
}
}
return a;
}*/

//Method that check whether the current position is valid
private static boolean IsValid(int[] board, int i) {

for (int j = i - 1, x = 1; j > -1; j--, x++)
if (board[i] == board[j] || board[i] + x == board[j] || board[i] - x == board[j])
return false;
return true;
}

//Method that print board
private static void PrintBoard(int[] board) {
System.out.print(" ");
for (int j = 0; j < board.length; j++)
System.out.print(" " + j + " ");
System.out.println();
for (int i = 0; i < board.length; i++) {
System.out.print(" " + i + " ");
for (int j = 1; j <= board.length; j++)
if (board[i] != j)
System.out.print(" ");
else
System.out.print(" Q ");
System.out.println();
}
}

public static void main(String[] args) {

// Determine the chess board size
Scanner input = new Scanner(System.in);
System.out.println("Enter the chess board size\n");
int n = input.nextInt();

//Creation of board
int[] board = new int[n];

//call solve method
long failure = NQueen(n, board, 0, false, 0);

System.out.println("Number of failure : " + failure);

//Printing board
PrintBoard(board);

}
}

2. 3. I've used a depth-first search in spy girlfriend software. We can discuss this problem if you are interested.