Eight queens puzzle with O(n) complexity

Problem Statement: (Wiki Definition):
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
                                 The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 and n=3.





There could be multiple solutions for this problem, What I mean to say is, there is multiple ways to arrange queens on a chess board. Different approaches might give different arrangements/outputs.

Possible Solution

• Backtracking algorithm
• Optimized Way

Backtracking Algorithm :

It starts with first row and place the Queen in the first cell. Once placed it will ignore the row, column and diagonal cell for next Queen. Proceed with next row and apply the same rule/logic. Keep repeating this until you get the solution. At any point if you see there is no more place left for QUEEN, It means all the above positions where Queen has been placed is not the correct cells,  Go back to previous row and try to find another place for the Queen. If you still don't find the place in this as well then move back to earlier one.

                             Keep repeating above process until you get the solution. As soon as, you get the solution stop the algorithm.







public class NQueenProblem {

private static int n = 8;
int[] array = new int[n];
int[][] chessBoard = new int[n][n];

private boolean[] status = new boolean[] { false };
/*
     * Whether Queen can be placed at this location or not.
     *
     * @Param row : ROW number
     *
     * @Param col : Column number
     *
     * @return boolean: true if queen can be place else false.
     */
    public boolean isQueuePlaced(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (array[i] == col
                    || Math.abs(array[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    public void NQueueProblemSol(int startRow, int queueRowSize) {
        for (int i = 0; i < queueRowSize; i++) {
            if (status[0]) {
                return;
            }
            if (isQueuePlaced(startRow, i)) {
                array[startRow] = i;
                Arrays.fill(chessBoard[startRow], 0);
                chessBoard[startRow][i] = 1;
                if (startRow == queueRowSize - 1) {
                    status[0] = true;
                    return;
                }
                int nextRow = (startRow + 1);
                NQueueProblemSol(nextRow, queueRowSize);
            }
        }
    }
}






Optimized Way:
 Instead of going to backtracking approach, We can place Queens in step fashion.

No Queen threaten each other in above image.


public class NQueenProblem {

    private static int n = 10;

    int[] array = new int[n];

    int[][] chessBoard = new int[n][n];

 public void NQueueProblemSol(int queueRowSize) {

        if(queueRowSize==1 || queueRowSize==2){
            chessBoard1[0][0]=1;
            return;
        }
        if(queueRowSize==3){
            chessBoard[0][0]=1;
            chessBoard[1][2]=1;
            return;
        }
        int r = queueRowSize - 1, c = queueRowSize - 2;
        for (int k = queueRowSize - 1; k >= 0; k--) {
            chessBoard[r][c] = 1;
            r = r - 1;
            if (c < 2) {
                c = queueRowSize - 1;
            } else {
                c = c - 2;
            }

        }

    }
 }



Above code has only one for loop which executes n times where n is the size of general board. This is the reason why Complexity of this program is O(n).