Solving N Queens Problem using Backtracking

Board Infinity
Board Infinity
Solving N Queens Problem using Backtracking

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search Algorithm?


Introduction

In this article, we will study a classic Backtracking problem. This is a considerably hard problem and implements several programming paradigms. The N-queens problem is something that chess enthusiasts will find interesting. Backtracking is a nice skill to comprehend. When regressing, we begin with one possible move out of a variety of options. Then, we attempt to resolve the issue. If the problem can be solved using the chosen move, the solution will be printed. If not, we will go back and choose another move to try to solve it. We assert that there is no solution to the problem if none of the moves succeed.

Scenarios and Steps

Problem Statement: How can N queens be arranged on a NxN chessboard without any of them attacking one another?

In interviews, N is usually considered to be 4 in the problem statement so for this article we will assume it to be the same,


Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There can be two possible movesets for the posed question

You must understand how the chess queen moves in order to solve this puzzle.

  1. A queen can move in any direction and take any number of steps.
  2. The only restriction is that it cannot reverse course while moving.
  3. The movement of the queen makes it obvious that no two queens can be found in the same row or column. As a result, we can only put one queen for each row and column.
  4. By positioning a queen at a position and attempting to rule out the possibility that it is being attacked, we attempt to solve this problem.
  5. Each row or column gets one queen. If we notice that the queen is being attacked at the position it has selected, we move on to the next one.
  6. If a queen is being attacked at each position in a row, we go back and move the queen who was in that position before the current one.
  7. Until all N queens are successfully placed, we keep doing this backtracking and placing a queen cycle.

Code

#define N 4
#include <stdbool.h>
#include <stdio.h>

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");
    }
}

// to determine whether a position [N][N] on the board is safe or not
bool isSafe(int board[N][N], int row, int col)
{
    int i, j;
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return false;
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return false;
 
    return true;
}

// critical function
bool solveNQUtil(int board[N][N], int col)
{
    if (col >= N)
        return true;
 
 
    for (int i = 0; i < N; i++) {
            if (isSafe(board, i, col)) {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1))
                return true;

            //if false, backtrack by resetting.
            board[i][col] = 0;
        }
    }
    return false;
}


int main()
{
    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 0;
    }
 
    printSolution(board);
    return true;
    return 0;
} 

write your code here: Coding Playground

Complexity Analysis

Since we are calculating every move and considering every single position on the chessboard for a possible move, even the optimized backtracking approach will yield a Time Complexity of O(N!) and the Auxiliary Space required will be constant O(N) since the size of the chessboard is fixed.