N-Queen Problem (BackTracking Algorithm)

Design and Analysis of Algorithm 

Abstract

Backtracking is a fundamental algorithmic technique used to solve problems that involve searching for solutions among a set of possible candidates, often where the solution must satisfy certain constraints. It visits all the possible solutions and returns if the solution does not meet the criteria. So we can say that it uses a more refined version of brute force searching style for a given problem. For example in the 0/1 knapsack problem, we use backtracking to assign the O’s and 1’s to the corresponding item’s weight.

1. Theory

1.1 Background:

The term “backtracking” was coined by D.H. Lehmer in the 1950s, with contributions from R.J. Walker, S.G. Golomb, and L. Baumert.

1.2 N-Queen Problem:

It is a type of classic backtracking problem where queens are placed on an n x n board in a such way that two queens cannot cross each other diagonally, row and column (diagonal, left, right, top, and down way).

There are two popular categories of the N-Queen Problem:

1. 4-queen problem (4 x 4 = 16 cell board)
2. 8-queen problem (8 x 8= 64 cell board)

2. Algorithm:

1. Place a queen in the first column of the first row.
2. Check if placing the queen in the current position conflicts with any previously placed queens.
3. If there is no conflict, proceed to the next column. If there is a conflict, backtrack to the previous column and try placing the queen in the next row.
4. Repeat steps 2 and 3 for all columns.
5. If all queens are placed successfully without conflicts, a solution is found.
6. If no solution is found after exploring all possibilities, backtrack to the previous column and try placing the queen in the next row.

For 8-Queens Problem

For the 8 x 8 problem, our tree structure will be 2⁸ = 256 unique nodes.

3. Program Implementation

#include <stdio.h>
#include <stdbool.h>

#define N 8

// Function prototypes
void printSolution(int board[N][N]);
bool isSafe(int board[N][N], int row, int col);
bool solveNQUtil(int board[N][N], int col);
bool solveNQ();

// Main driver function
int main() {
    solveNQ();
    return 0;
}

// Function to print 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");
    }
    printf("\n");
}

// Function to check if a queen can be placed on board[row][col]
bool isSafe(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;
}

// Function to solve the N-Queens problem using backtracking
bool solveNQUtil(int board[N][N], int col) {
    // If all queens are placed
    if (col >= N)
        return true;

    // Try placing this queen in all rows one by one
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            // Place this queen in board[i][col]
            board[i][col] = 1;

            // Recur to place the rest of the queens
            if (solveNQUtil(board, col + 1))
                return true;

            // If placing queen in board[i][col] doesn't lead to a solution
            // then remove the queen from board[i][col]
            board[i][col] = 0;
        }
    }

    // If the queen cannot be placed in any row in this column
    return false;
}

// Function to solve the N-Queens problem
bool solveNQ() {
    int board[N][N] = {0}; // Initialize the board with 0s

    if (solveNQUtil(board, 0) == false) {
        printf("Solution does not exist");
        return false;
    }

    printSolution(board);
    return true;
}        

4. Discussion

4.1 Why study N-Queen Problems?

Artificial Intelligence(Game theory, Machine Learning), Robotics(Path-Planing), Scheduling Algorithms, Scheduling, and Resource Allocation are some of the applications of this abstract problem. It also provides insights, computational interest, and optimization to the problems.

4.2 Time Complexity Analysis

The time complexity of the N-Queens problem using backtracking can be analyzed as follows:

• Worst-case Time Complexity: In the worst case, the algorithm might explore all possible configurations of the board. For each row, it tries to place a queen in all columns and checks for safety. Therefore, the time complexity can be approximated as O(N!) because there are N! possible permutations of queens on the board.

4.3 Practical Performance: The actual number of configurations explored is much less than N! because the algorithm prunes many configurations early (when it detects conflicts), making the practical performance much better than the worst-case scenario. But it is still N! which makes matters concerning and should not take a large number of n x n board.

5. Conclusion:

Hence we studied the Backtracking algorithms as being those classes of classical optimization that take/find all the sub-solutions of the problems within a constraint and often move back and forward for the solutions. In the general method, it would take subset solutions of n-tuple ie. xi = {x1,x2…..xn). 

6. References:

1. LLMs (Coding)
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Computer Algorithms”, Second Edition, Silicon Press, 2007.

Read More Articles on Dilli Hang Rai | LinkedIn

More About me: dilli822.github.io

Feedback & Review: dillihangrae@gmail.com, dillihagrai.078@godawari.edu.np