ADA Program 12

Program 12 — N Queens (Backtracking)

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

#define MAX 10

int SolnCount = 0;

void fnChessBoardShow(int n, int colVec[MAX]);
bool fnCheckPlace(int kthQueen, int colNum, int colVec[MAX]);
int NQueen(int k, int n, int colVec[MAX]);

int main(void) {
    int n;
    int colVec[MAX];
    printf("Enter the number of queens: ");
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        colVec[i] = -1;
    printf("\nSolutions for %d-Queens problem:\n", n);
    if (!NQueen(0, n, colVec))
        printf("No solution exists for %d queens.\n", n);
    else
        printf("\nTotal solutions found: %d\n", SolnCount);
    return 0;
}

int NQueen(int k, int n, int colVec[MAX]) {
    if (k == n) {
        fnChessBoardShow(n, colVec);
        SolnCount++;
        return 1;
    }
    
    for (int i = 0; i < n; i++) {
        if (fnCheckPlace(k, i, colVec)) {
            colVec[k] = i;
            if (!NQueen(k + 1, n, colVec)) {
                colVec[k] = -1;
            }
        }
    }
    return 0;
}

bool fnCheckPlace(int kthQueen, int colNum, int colVec[MAX]) {
    for (int i = 0; i < kthQueen; i++) {
        if (colVec[i] == colNum ||
            abs(colVec[i] - colNum) == abs(i - kthQueen))
            return false;
    }
    return true;
}

void fnChessBoardShow(int n, int colVec[MAX]) {
    printf("\nSolution #%d:\n", SolnCount + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j == colVec[i])
                printf("Q ");
            else
                printf("# ");
        }
        printf("\n");
    }
    printf("\n");
}