N Queen Problem Analysis

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

For a larger N, this problem couldn’t be solved in polynomial time. So, it is an NP-Complete problem. However, this problem could be solved by backtracking in non-polynomial time for a smaller N.

Solution of N Queen problem using backtracking checks for all possible arrangements of N Queens on the chessboard. And then checks for the validity of the solution. The code for the problem is below:

//
//  main.cpp
//  N Queen
//
//  Created by Himanshu on 22/04/22.
//

#include <iostream>
#include <cstdio>
#define N 8


// This function prints the solution
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf(" %d ", board[i][j]);
        }
        printf("\n");
    }
}

// A function to check if a queen can
// be placed on board[row][col].
bool check(int board[N][N], int row, int col) {
    int i, j;

    // Check this row on left side
    for (i = 0; i < col; i++) {
        if (board[row][i]) {
            return false;
        }
    }
    
    // Check upper diagonal on left side
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return false;
        }
    }
    
    // Check lower diagonal on left side
    for (i = row, j = col; j >= 0 && i < N; i++, j--) {
        if (board[i][j]) {
            return false;
        }
    }
    
    return true;
}


// A recursive function to solve N Queen problem
bool solveUtil(int board[N][N], int col)
{
    // Base case: If all queens are placed then return true
    if (col >= N) {
        return true;
    }
    
    for (int i = 0; i < N; i++) {
        
        // Check if the queen can be placed
        if (check(board, i, col)) {
            board[i][col] = 1;
            
            // recur to place rest of the queens
            if (solveUtil(board, col + 1)) {
                return true;
            }
            
            board[i][col] = 0; // Backtrack
        }
    }
    
    return false;
}


int main() {
    int board[N][N] = {0};
    
    if (solveUtil(board, 0) == false) {
        printf("Solution does not exist");
    } else {
        printf("Solution:\n");
        printSolution(board);
    }
    
    return 0;
}

Output

 1  0  0  0  0  0  0  0 
 0  0  0  0  0  0  1  0 
 0  0  0  0  1  0  0  0 
 0  0  0  0  0  0  0  1 
 0  1  0  0  0  0  0  0 
 0  0  0  1  0  0  0  0 
 0  0  0  0  0  1  0  0 
 0  0  1  0  0  0  0  0 

Here is a working example – N Queen solution. (Try changing the value of N)

Now number of possible arrangements of N Queens on N x N chessboard is N!, given you are skipping row or column, already having a queen placed.
So average and worst case complexity of the solution is O(N!) (since, you are checking all the possible solutions i.e. N^N arrangements). The best case occurs if you find your solution before exploiting all possible arrangements. This depends on your implementation. Also there could be more than one solution for this problem, but we stop as soon as we find one feasible solution to the problem.

And if you need all the possible solutions, the best, average and worst case complexity remains O(N!).

One thought on “N Queen Problem Analysis

Leave a Reply

Your email address will not be published.