八皇后问题 在8×8格的棋盘上放置彼此不受攻击的8个皇后。 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 八皇后问题等价于在8×8格的棋盘上放置8个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 要求：分别用子集树框架和排列树框架编写C语言程序实现八皇后问题

子集树框架实现八皇后问题的C语言程序：

#include <stdio.h>

#define N 8

int row[N], col[N], diag1[2*N-1], diag2[2*N-1];
int count = 0; // 记录解的个数

void printSolution() {
    int i, j;
    printf("Solution %d:\n", ++count);
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (row[i] == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

void backtrack(int c) {
    int r;
    if (c == N) {
        printSolution();
        return;
    }
    for (r = 0; r < N; r++) {
        if (!col[r] && !diag1[r+c] && !diag2[r-c+N-1]) {
            row[c] = r;
            col[r] = diag1[r+c] = diag2[r-c+N-1] = 1;
            backtrack(c+1);
            col[r] = diag1[r+c] = diag2[r-c+N-1] = 0;
        }
    }
}

int main() {
    backtrack(0);
    return 0;
}

排列树框架实现八皇后问题的C语言程序：

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

#define N 8

int col[N], diag1[2*N-1], diag2[2*N-1];
int count = 0; // 记录解的个数

void printSolution(int row[]) {
    int i, j;
    printf("Solution %d:\n", ++count);
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (row[i] == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

void backtrack(int row[]) {
    int i, j, temp;
    if (row[N-1] != -1) {
        printSolution(row);
        return;
    }
    for (i = 0; i < N; i++) {
        if (!col[i] && !diag1[row[0]+i] && !diag2[row[0]-i+N-1]) {
            row[0] = i;
            col[i] = diag1[row[0]+i] = diag2[row[0]-i+N-1] = 1;
            backtrack(row);
            col[i] = diag1[row[0]+i] = diag2[row[0]-i+N-1] = 0;
        }
    }
    for (i = 1; i < N; i++) {
        if (row[i] == -1) {
            for (j = i; j < N; j++) {
                if (row[j] != -1) {
                    temp = row[i];
                    row[i] = row[j];
                    row[j] = temp;
                    break;
                }
            }
            for (j = 0; j < N; j++) {
                if (!col[j] && !diag1[row[i]+j] && !diag2[row[i]-j+N-1]) {
                    col[j] = diag1[row[i]+j] = diag2[row[i]-j+N-1] = 1;
                    backtrack(row);
                    col[j] = diag1[row[i]+j] = diag2[row[i]-j+N-1] = 0;
                }
            }
            temp = row[i];
            for (j = i; j > 0; j--) {
                row[j] = row[j-1];
            }
            row[0] = temp;
        }
    }
}

int main() {
    int i, row[N];
    for (i = 0; i < N; i++) {
        row[i] = -1;
    }
    backtrack(row);
    return 0;
}