Solving of N-Queens Problem using Backtracking

Problem Statement

Given an integer N, your goal is to find all possible arrangements to place N queens on an N×N chessboard. This can be solved using backtracking, a technique that tries to build a solution incrementally and abandons a solution as soon as it determines that it cannot be valid.

Key Concepts

1. Backtracking: This algorithm explores all possible placements of queens row by row and backtracks when it encounters a conflict.
2. Safety Check: Before placing a queen, we need to ensure that it doesn’t threaten other queens already placed on the board.

Steps to Solve the Problem

1. Board Representation: Use a 2D array to represent the chessboard.
2. Placement: For each row, attempt to place a queen in every column.
3. Validation: Check if placing the queen is valid (i.e., no queens threaten each other).
4. Recursive Call: If placing the queen is valid, make a recursive call to place queens in the next row.
5. Backtrack: If a placement doesn’t lead to a solution, remove the queen and try the next column.

C Program to Solve the N-Queens Problem

#include <stdio.h>
#include <stdbool.h>

#define N 8 // Change this value to solve for different sizes

// Function to print the chessboard
void printBoard(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");
    }
    printf("\n");
}

// Function to check if a queen can be placed at board[row][col]
bool isSafe(int board[N][N], int row, int col) {
    // Check this column on upper rows
    for (int i = 0; i < row; i++)
        if (board[i][col]) return false;

    // Check upper diagonal on the left side
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return false;

    // Check upper diagonal on the right side
    for (int i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j]) return false;

    return true;
}

// Function to solve the N-Queens problem using backtracking
bool solveNQUtil(int board[N][N], int row) {
    // Base case: If all queens are placed
    if (row >= N) {
        printBoard(board);
        return true;
    }

    // Try placing a queen in each column of the current row
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            // Place queen
            board[row][col] = 1;

            // Recursively place the rest of the queens
            if (solveNQUtil(board, row + 1)) {
                return true; // If successful, return true
            }

            // Backtrack: Remove the queen
            board[row][col] = 0;
        }
    }
    return false; // No valid position found
}

// Main function
int main() {
    int board[N][N] = {0}; // Initialize the board with 0s

    printf("Solutions for %d-Queens Problem:\n", N);
    if (!solveNQUtil(board, 0)) {
        printf("No solution exists\n");
    }

    return 0;
}

Explanation of the Code

1. Board Representation: A 2D array board[N][N] is used to represent the chessboard. A value of 1 indicates a queen is placed in that position, and 0 indicates an empty position.
2. Printing the Board: The printBoard function displays the current state of the board.
3. Safety Check: The isSafe function checks whether a queen can be placed at a given position (row, col) by checking the column and the diagonals.
4. Backtracking Function: The solveNQUtil function attempts to place queens row by row. If it successfully places all queens, it prints the board configuration. If it cannot place a queen in any column, it backtracks by removing the last placed queen.
5. Main Function: Initializes the board and starts the backtracking process. It prints all possible solutions.

Input and Output Example

Input

The program is currently set to solve the 8-Queens problem (N=8) as defined by the macro #define N 8.

Output

The program outputs all possible configurations for placing 8 queens on the board.

Example output:

codeSolutions for 8-Queens Problem:
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 

... (more solutions)

Explanation of the Output

Each configuration shows a possible arrangement of the queens on the chessboard, where 1 represents a queen and 0 represents an empty space. The output may contain multiple solutions depending on the size of N.

Conclusion

This program effectively implements the N-Queens problem using backtracking. It showcases how to systematically explore possible placements and use recursion to find all valid solutions. You can modify the value of N to solve for different sizes of the chessboard.