Kill Backtrack: N Queen Problem of Chess

Problem statement: You are given a N x N (N cross N) board. And N queens. You have to design an algorithm to place those N queens in N x N board, so that none of the queens are clashing.

Example: if the board is 1 x 1, then I can place the 1 queen at (0, 0) grid.

if board is 2 x 2, then I cannot place 2 queens. They will definitely clash, and no solution exists for this.

for board 3 x 3, also it’s not possible to get the gird arrangement of queens.

Assume the board size is greater than or equals to 4 x 4.

for 4 x 4, I can place four queens at    (0, 1) , (1, 3), (2, 0), (3, 2).

Given the size of the grid as N, return the possible arrangement.

Solution Approach:   This problem is also solvable by back-tracking :

1. Start in the topmost row.

2. If all queens are placed return true

3. Try all columns in the current row.

Do the following  for every tried column:

a). If the queen can be placed safely in this column then mark this[row, column] as part of the solution and recursively check if placing

queen here leads to a solution.

b). If placing queen in [row, column] leads to a solution then return true.

c). If placing queen doesn’t lead to a solution then unlock this [row, column] (backtrack) and go to step (a) to try for other columns.

4. If all the columns have been tried and nothing worked, return false to trigger backtracking.

You can play N-queen back tracking in:

http://www.hbmeyer.de/backtrack/achtdamen/eight.htm#up

The implementation in Java for the same is given below

public class NQueens
{
    private static int n;
    private static int[] columns;

    public static void placeQueen(int row)
    {
        if(row == n - 1) // we have taken all the n rows.
        {
            for(int i = 0; i < n; i++) System.out.print("( " + i + ", " + columns[i] + ") " );
            System.out.println();
        }
       else
       {
           if(isSafe(row))
           {
               for(int i = 0; i < n; i++)
               {
                   columns[row + 1] = i;
                   placeQueen(row + 1);
               }
           }
       }
    }

    public static boolean isSafe(int row)
    {
        int k = 0; boolean flag = true;
        while(k < row && flag)
        {
            if(columns[row] == columns[k] || Math.abs(columns[row] - columns[k]) == Math.abs(row - k))
                flag = false;
            k++;
        }
        return flag;
    }

    public static void main(String[] args)
    {
        n = 8;
        columns = new int[n];
        placeQueen(0);
    }
}

Worst case bound for this algorithm is worse than the order of exponential.