This code implements the N-Queens problem using backtracking. It finds...

April 23, 2024 at 05:49 AM

#include <stdio.h>

#define MAX 10

int isSafe(int board[MAX][MAX], int row, int col, int n) {
    int i, j;

    // Check for the current row
    for(i = 0; i < col; i++)
        if(board[row][i])
            return 0;

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

    // Check for the lower left diagonal
    for(i = row, j = col; j >= 0 && i < n; i++, j--)
        if(board[i][j])
            return 0;

    return 1;
}

int nQueen(int board[MAX][MAX], int col, int n) {
    if(col >= n)
        return 1;

    int i;
    int res = 0;

    for(i = 0; i < n; i++) {
        if(isSafe(board, i, col, n)) {
            board[i][col] = 1;
            res += nQueen(board, col + 1, n);
            board[i][col] = 0; // backtracking
        }
    }

    return res;
}

int main() {
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);

    int board[MAX][MAX] = {0};

    int count = nQueen(board, 0, n);
    printf("The number of solutions is: %d\n", count);

    return 0;
}

This code implements the N-Queens problem using backtracking. It finds and counts the number of ways to place N queens on an NxN chessboard such that no two queens threaten each other. The isSafe function checks if it is safe to place a queen at a given position on the board, and the nQueen function recursively tries to place queens on each column of the board while maintaining the safety constraints. Finally, the main function takes the input value of N, initializes the chessboard, calls the nQueen function to find the number of solutions, and prints the count of valid solutions.

Generate your own explanations

Download our vscode extension

Read other generated explanations

Built by @thebuilderjr