C++Program to Solve N-Queens Problem Using Backtracking

Table of Contents

Introduction

The N-Queens problem is a classic example of combinatorial optimization and backtracking. It involves placing N chess queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal. The problem is a fundamental example of the application of backtracking algorithms and is often used to teach the concept of constraint satisfaction in computer science.

In this article, we will discuss the N-Queens problem, explain the backtracking approach to solve it, and provide a C++ program with examples to illustrate the solution and outputs.

Prerequisites

Before diving into the implementation, it’s beneficial to have:

Basic understanding of algorithms: Knowledge of backtracking and recursion.
Familiarity with C++ programming: Proficiency in C++ syntax, arrays, and functions.

The N-Queens Problem

Definition and Formula

The N-Queens problem is defined as placing N queens on an N×N chessboard such that no two queens threaten each other. A queen can move horizontally, vertically, or diagonally, meaning that for a valid arrangement:

No two queens share the same row.
No two queens share the same column.
No two queens share the same diagonal.

The solution to the N-Queens problem can be approached using backtracking, a technique for solving constraint satisfaction problems. Backtracking incrementally builds candidates for the solution and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly lead to a valid solution.

Implementing the N-Queens Problem in C++

1.1 Backtracking Approach

Below is a C++ implementation of the N-Queens problem using backtracking.

C++

#include <iostream>
#include <vector>
#define N 4

void printSolution(const std::vector<std::vector<int>>& board) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            std::cout << board[i][j] << " ";
        std::cout << std::endl;
    }
}

bool isSafe(const std::vector<std::vector<int>>& board, int row, int col) {
    for (int i = 0; i < col; i++)
        if (board[row][i])
            return false;

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return false;

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

    return true;
}

bool solveNQUtil(std::vector<std::vector<int>>& board, 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;
            board[i][col] = 0; // BACKTRACK
        }
    }
    return false;
}

bool solveNQ() {
    std::vector<std::vector<int>> board(N, std::vector<int>(N, 0));
    if (!solveNQUtil(board, 0)) {
        std::cout << "Solution does not exist" << std::endl;
        return false;
    }
    printSolution(board);
    return true;
}

int main() {
    solveNQ();
    return 0;
}

1.2 Example Usage

The example above initializes the N-Queens problem with a 4×4 chessboard. The output will show a possible solution to the problem.

1.3 Output for Example 1

C++

Additional Examples

2.1 Example 2: 8-Queens Problem

In this example, we increase the number of queens to 8 to illustrate how the solution scales.

C++

#define N 8

int main() {
    solveNQ();
    return 0;
}

Output for Example 2

C++

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

2.2 Example 3: Customizing the Board Size

Here, we solve the N-Queens problem for a 5×5 board.

C++

#define N 5

int main() {
    solveNQ();
    return 0;
}

Output for Example 3

C++

Conclusion

The N-Queens problem is an excellent example of the power of backtracking algorithms. It demonstrates how complex problems can be broken down into smaller, manageable subproblems, making it a valuable teaching tool in computer science. This article provided a detailed C++ implementation of the N-Queens problem, complete with examples and outputs to illustrate its practical application. Understanding and implementing this problem enhances your problem-solving skills and provides a solid foundation in recursive and backtracking techniques.