Backtracking Algorithm in C: Solving the Eight Queens Problem

Introduction

The Eight Queens problem is a classic combinatorial optimization problem that requires placing 8 queens on an 8×8 chessboard such that no two queens threaten each other. In other words, no two queens can be in the same row, column, or diagonal. This problem can be effectively solved using the backtracking algorithm.

This article will detail how to implement a solution to the Eight Queens problem using C language, explaining each part of the code step by step.

Introduction to Backtracking Algorithm

The backtracking algorithm is a method for finding all possible solutions by constructing a solution space tree. During the solving process, if it is found that the current path cannot yield a valid solution, it will “backtrack” to the previous step and try other possibilities. This method is particularly suitable for combinatorial problems such as permutations, combinations, and graph covering.

Basic Idea of the Eight Queens Problem

Define the Chessboard: Use an array to represent the chessboard, where the array index represents the row number and the array value represents the column number.
Recursive Placement: Start from the first row and recursively attempt to place queens, choosing a column position each time.
Legitimacy Check: Before placing each new queen, check if the position is safe (i.e., does not conflict with any already placed queens).
Find Solutions: If all 8 queens are successfully placed, record this set of solutions.
Backtrack: If a path cannot continue, undo the last operation and try the next possible position.

C Language Implementation

Below is the complete code for the Eight Queens problem implemented in C:

#include <stdio.h>
#include <stdbool.h>
#define N 8 // Chessboard size is 8x8
int board[N]; // Used to store the position of queens in each row
int solutionCount = 0; // Solution counter
// Function declarations
void printSolution();
bool isSafe(int row, int col);
void solveNQueens(int row);
int main() {
    solveNQueens(0); // Start solving from row 0
    printf("Total %d different arrangements found.\n", solutionCount);
    return 0;
}
// Print the current solution
void printSolution() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i] == j) {
                printf(" Q ");
            } else {
                printf(" . ");
            }
        }
        printf("\n");
    }
    printf("\n");
}
// Check if the position (row, col) is safe
bool isSafe(int row, int col) {
    for (int i = 0; i < row; i++) {
        // Check for column and diagonal conflicts
        if (board[i] == col ||
            board[i] - i == col - row ||
            board[i] + i == col + row) {
            return false;
        }
    }
    return true;
}
// Solve the N-Queens problem using recursion
void solveNQueens(int row) {
    if (row == N) { // All queens have been successfully placed
        printSolution(); // Print the current solution
        solutionCount++; // Increment the counter
        return;
    }
    for (int col = 0; col < N; col++) {
        if (isSafe(row, col)) {
            board[row] = col; // Place queen at the current position
            solveNQueens(row + 1); // Try the next row
            // No need to explicitly backtrack, as we directly overwrite board[row]
        }
    }
}

Program Analysis

Global Variable Definitions

board[N] array is used to store the position of queens in each row. For example, if board[2] = 3, it indicates that the queen in the third row (index 2) is in the fourth column (index 3).
solutionCount is used to count how many different arrangements have been found.

Main Function

Calls solveNQueens(0) to start solving from the first row and ultimately outputs how many arrangements have been found.

Print Solution

printSolution() function is responsible for formatting and outputting the current valid layout, using Q to represent queens and dots for empty squares.

Safety Check

In the isSafe() function, we iterate through the already placed queens to ensure that the new position does not conflict with existing positions, including checks for the same column and both diagonal conflicts.

Recursive Solution

In the solveNQueens() function, we loop through each column, placing the queen in the corresponding position if it is safe, and then recursively call itself to handle the next level. If the placement reaches the last level, meaning all queens are correctly placed, it prints the result and increments the counter.

Conclusion

Through the above code, we have implemented the classic Eight Queens problem using C language and demonstrated how to apply the backtracking algorithm for depth-first search. I hope this article helps you understand the backtracking algorithm and its applications, while also inspiring you to explore more complex problems!