Objective

The N-Queens problem is a classic combinatorial problem that asks how to place N queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal. The goal is to find all possible arrangements of the queens on the board.

C Program

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

int board[MAX][MAX];
int N;

void printSolution() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf(" %d ", board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int isSafe(int row, int col) {
    for (int i = 0; i < col; i++)
        if (board[row][i]) return 0;

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

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

    return 1;
}

int solveNQUtil(int col) {
    if (col >= N) {
        printSolution();
        return 1;
    }

    int res = 0;
    for (int i = 0; i < N; i++) {
        if (isSafe(i, col)) {
            board[i][col] = 1;
            res = solveNQUtil(col + 1) || res;
            board[i][col] = 0; // backtrack
        }
    }
    return res;
}

void solveNQ() {
    solveNQUtil(0);
}

int main() {
    printf("Enter the number of queens: ");
    scanf("%d", &N);
    if (N >= 4) {
        // Initialize the board with 0
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                board[i][j] = 0;

        solveNQ();
    } else {
        printf("No solution exists for N < 4\n");
    }
    return 0;
}

Program Structure

The program consists of several key functions:

• printSolution: Prints the current arrangement of queens on the board.
• isSafe: Checks if placing a queen at a given position is safe (i.e., no queens threaten each other).
• solveNQUtil: A recursive utility function that attempts to place queens in a column and backtracks if a conflict occurs.
• solveNQ: Initiates the solving process.
• main: Entry point of the program that takes user input for the number of queens.

How to Run the Program

To run this program, follow these steps:

1. Copy the code into a text file and save it with a .c extension, for example, nqueens.c.
2. Open a terminal or command prompt.
3. Navigate to the directory where you saved the file.
4. Compile the program using a C compiler, such as GCC:

   gcc nqueens.c -o nqueens

5. Run the compiled program:

   ./nqueens

6. Enter the number of queens (N) when prompted. The program will output all possible solutions.