Solving the N Queen Problem with C

Solving the N-Queen Problem with C. The N-Queen Problem is a classic algorithmic challenge that involves placing N queens on an N*N chessboard so that no two queens can threaten each other. This means two queens can be in the same row, column, or diagonal. This article provides a step-by-step guide to solving the n queen problem with C language, focusing on a backtracking approach, which is a form of recursive algorithm.

Understanding the N Queen Problem

Before jumping into coding, it is crucial to thoroughly understand what the n queen problem is and what it entails. the goal is to find all the problem arrangments of n queen on an n*n chessboard where no two queens attack each other.

Solving N Queen Problem with C

Defining the Chessboard

The chessboard can be represented as a 2D array of integers, where 0 indicates a space and 1 represents a queen.

int board[n][n];

Initializing the Chessboard

Before starting ensure that the chessboard is empty. this can be done with the simple nested loop

void initalizeBoard(int board[n][n])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            board[i][j] = 0;
        }
    }
}

Check if the Queen can be Placed

We need a function to check if a queen can be placed on the board at the [row][col] position without being attacked by another queen.

int isSafe(int board[n][n], int row, int column)
{
    int i, j;
    // Check this row on left side
    for (i = 0; i < column; i++)
    {
        if (board[row][i])
        {
            return 0;
        }
    }
    // Check upper diagonal on upper side
    for (i = row, j = column; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
        {
            return 0;
        }
    }
    // Check lower diagonal on left side
    for (i = row, j = column; j >= 0 && i < n; i++, j--)
    {
        if (board[i][j])
        {
            return 0;
        }
    }
    return 1;
}

Solve the N Queen Problem

Use backtracking to solve the problem recursively. the function tries to place a queen on every row. if placing a queen in a certain column leads to the solution, it proceeds to place another queen in the next row. If it does not lead to a solution, it backtracks and tries a different column.

  int solvenqueen(int board[n][n], int column)
{
    // Base case: If all queens are placed
    if (column >= n)
    {
        return 1;
    }
    // Consider this column and try placing this queen in all rows one by one
    for (int i = 0; i < n; i++)
    {
        // Chcek if queen can be placed on board[i][column]
        if (isSafe(board, i, column))
        {
            // Place this queen on board[i][column]
            board[i][column] = 1;
            // Recur to place rest of the queens
            if (solvenqueen(board, column + 1))
            {
                return 1;
            }
            // If placing queens in board[i][column] does not need to a solution,
            board[i][column] = 0;
        }
    }
    // if the queen can't be placed in any row in this column then return false
    return 0;
}

Implement the Main Function

This function initializes the board and calls the utility function to solve the problem.

void main()
{
    printf("Enter the value of n ");
    scanf("%d", &n);
    int board[n][n];
    initalizeBoard(board);
    if (!solvenqueen(board, 0))
    {
        printf("Solution does not exist");
    }
    else
    {
        printSolution(board);
    }
}

Print the Solution

Implement a function to print the chessboard with a Queen place.

void printSolution(int board[n][n])
{
    printf("\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\n");
}

Compelet C Program for N Queen Problem

#include <stdio.h>
#include <stdlib.h>
int n;
void printSolution(int board[n][n])
{
    printf("\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\n");
}
int isSafe(int board[n][n], int row, int column)
{
    int i, j;
    // Check this row on left side
    for (i = 0; i < column; i++)
    {
        if (board[row][i])
        {
            return 0;
        }
    }
    // Check upper diagonal on upper side
    for (i = row, j = column; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
        {
            return 0;
        }
    }
    // Check lower diagonal on left side
    for (i = row, j = column; j >= 0 && i < n; i++, j--)
    {
        if (board[i][j])
        {
            return 0;
        }
    }
    return 1;
}
int solvenqueen(int board[n][n], int column)
{
    // Base case: If all queens are placed
    if (column >= n)
    {
        return 1;
    }
    // Consider this column and try placing this queen in all rows one by one
    for (int i = 0; i < n; i++)
    {
        // Chcek if queen can be placed on board[i][column]
        if (isSafe(board, i, column))
        {
            // Place this queen on board[i][column]
            board[i][column] = 1;
            // Recur to place rest of the queens
            if (solvenqueen(board, column + 1))
            {
                return 1;
            }
            // If placing queens in board[i][column] does not need to a solution,
            board[i][column] = 0;
        }
    }
    // if the queen can't be placed in any row in this column then return false
    return 0;
}
void initalizeBoard(int board[n][n])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            board[i][j] = 0;
        }
    }
}
void main()
{
    printf("Enter the value of n ");
    scanf("%d", &n);
    int board[n][n];
    initalizeBoard(board);
    if (!solvenqueen(board, 0))
    {
        printf("Solution does not exist");
    }
    else
    {
        printSolution(board);
    }
}

Output of N Queen Solution

n = 8

n=12

N Queen Problem Time Complexity

The backtracking approach for solving the n queen problem, as demonstrated in this article by using C language, does not have a straightforward time complexity due to its recursive nature and the fact that it explores multiple branches of execution, backtracking when a potential solution does not lead to success. The worst-case time complexity for the n queen problem using backtracking can be roughly estimated as O(n!) where n is the number of queens(or the size of the chessboard). This factorail time complexity arises because, in the worst case, the algorithm might need to try all possible arrangements of n queens on the board.

Happy Coding & Learning