Eight Queen Problem With Complete Solution In C

Many successful programmers know more than just a computer language. They also know how to think about solving problems. They use “computational thinking", i.e., breaking a problem down into segments that lend themselves to technical solution. Here, I took a real life problem and solved the problem in computer language. This time, I have taken a very famous problem known as the Eight Queen Problem.

 

Now, the question arises what is an "Eight Queen Problem"? The Eight Queen Problem, also known as Eight Queen Puzzle, is a problem of placing eight queens on an 8 x 8 chessboard so that none of them attack one another. By attacking, we mean no two are in the same row, column or diagonal. Eight Queen Problem is a form of more generalized problem known as N Queen Problem or N Queen Puzzle where you have to place the N queens on an N x N chessboard such a way that none of them attack one another.

 

Before we begin to solve, there are some prerequisites that all my readers must fulfill. As it is clear from the article that we are going to solve the problem in C language, the readers must be familiar with C. Also, the readers must know the fundamentals of arrays and recursion and how to use them. Before jumping to my solution, I request you to try to create your own solution. This will help in developing your own logic. So, let’s begin.

There are two possible solutions to this problem. One is called the Naive algorithm and the other one is called Backtracking Algorithm.

Naive Algorithm

In Naive Algorithm, we generate all possible configurations of queen on board and test each configuration until we find a configuration which satisfies all the conditions. This solution looks quite easy but it takes a lot of time, especially when the value of N is higher. As the size of the problem grows, the number of configuration also grows exponentially and so is the time.

Backtracking algorithm

In this method, we place the queens one by one in different columns starting from the leftmost column. Whenever we place a queen in a column, we check for clashes with already placed queens. If there is no clash, we mark this row and column as part of the solution. If we are unable to find a row to place the queen due to clashes, then we backtrack and return false. This means that the solution does not exist.

 You can see the source code below.

#include < stdio.h >
#include < conio.h >
#include < Windows.h >
#define N 8
//This method is used to color the characters
void Color(int col) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, col);
}
//This method print the final solution
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 1) {
                Color(2);
                printf("%d ", board[i][j]);
            } else {
                Color(15);
                printf("%d ", board[i][j]);
            }
        }
        printf("\n");
    }
}
//This method checks whether it is safe to place the queen in particular row and column.
//This will return true if it is safe to place the queen and false otherwise.
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;
}
//A recursive utility problem to solve N queens problem.
bool solveNQUtil(int board[N][N], int col) {
    /* base case: If all queens are placed
    then return true */
    if (col >= N) return true;
    /* Consider this column and try placing
    this queen in all rows one by one */
    for (int i = 0; i < N; i++) {
        /* Check if queen can be placed on
        board[i][col] */
        if (isSafe(board, i, col)) {
            /* Place this queen in board[i][col] */
            board[i][col] = 1;
            /* recur to place 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 queen from board[i][col] */
            board[i][col] = 0; // BACKTRACK
        }
    }
    /* If queen can not be place in any row in
    this colum col then return false */
    return false;
}
/* This function solves the N Queen problem using
Backtracking. It mainly uses solveNQUtil() to
solve the problem. It returns false if queens
cannot be placed, otherwise return true and
prints placement of queens in the form of 1s.
Please note that there may be more than one
solutions, this function prints one of the feasible soutions*/
bool solveNQ() {
    int board[N][N] = {
        {
            0,
            0,
            0,
            0
        },
        {
            0,
            0,
            0,
            0
        },
        {
            0,
            0,
            0,
            0
        },
        {
            0,
            0,
            0,
            0
        }
    };
    if (solveNQUtil(board, 0) == false) {
        printf("Solution does not exist");
        return false;
    }
    printSolution(board);
    return true;
}
int main() {
    solveNQ();
    _getch();
    return 0;
}

That's all for today guys! You can visit my blog.