**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[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); } }

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

ReplyDelete/*

* 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[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;

}*/

//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);

}

}

thanx

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

ReplyDelete