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

2 comments:

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

    }
    }

    ReplyDelete