C语言-N皇后问题

什么是N皇后问题？
在一个 N×N 国际象棋盘上,有 N 个皇后, 每个皇后占一格; 要求皇后间不会出现相互“攻击”的现象, 即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法.

分析：
用程序代码实现的时候，有两个核心模块，一个是检查能否在棋盘里的第n行放入皇后，另一个就是算出解及解的总数。我们要检查的时候，必然会涉及到行和列这两个数据，那么怎么处理会比较好呢？当然是越简单的方法越好，所以，我想可以用一维数组来处理这两个数据，利用数组元素的下标表示皇后所在的行，元素的值表示所在的列，比如q[i]=j就表示皇后在第i行第j列。那么现在有了这个，我们要关心的就是怎样去符合题目条件了。要能够在第n行放入一个皇后的话，那么它上面的第0到第n-1行都应该符合条件，即要用一次循环，循环检查让i从0~n-1变化，每一次的q[i]和q[n]都要满足一定的关系，只要有一次的检查不满足，那皇后就不能在第n行放入。
题目要求皇后不能在同一行和同一列，显然根据上面的分析，不会在同一行，那么怎样保证不会在同一列？只要q[i]!=q[n]就好了；然后如何保证皇后不会在同一对角线上，请看：

蓝色是主对角线，比如我们要检测在第3行能否放入皇后，则第三行皇后的坐标为(n:3,q[n]:3)，和它同一对角线上的坐标(i,q[i])分别为(0,0),(1,1),(2,2),可以知道，有这么一个关系：q[n]-q[i]=n-i。红色是副对角线，第三行皇后的坐标为(n:3,q[n]:0)，和它同一对角线上的坐标(i,q[i])分别为(0,3),(1,2),(2,1),可以知道，他们的关系为q[n]-q[i]=i-n，合并q[n]-q[i]=n-i和q[n]-q[i]=i-n为：abs(q[n]-q[i])==n-i。所以，经过分析，可以写出最终代码为：

//
//  Created by 刘铷斐@FZU on 15/4/18.
//  Copyright (c) 2015年 刘铷斐@FZU. All rights reserved.
//

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

int sum = 0;    // 解的总数
int * q = NULL; // 皇后棋盘
int max = 0;    // 皇后数量

/**
 *  输出皇后的解
 *  
 *  @return void
 */
void show() {
    int i, j;
    for(i=0; i<max; i++) {
        for(j=0; j<max; j++) {
            // 如果当前列是放皇后的位置，就输出Q，否则输出.
            if(q[i] == j) {
                printf("%2s", "Q");
            } else {
                printf("%2s", ".");
            }
        }
        printf("\n");
    }
    printf("\n");
}

/**
 *  检查第row行能否放下皇后，如果能放得下皇后，就返回1，否则返回0
 *
 *  @param int row - 要检测的行
 *  @param int maxQueens - 皇后总数量
 */
int checkValid(int row) {
    int i;
    // 将要放置那行和上面的几行逐一比较，只有都可以放置皇后后，才会返回1，否则返回0
    for(i=0; i< row; i++) {
        if(q[i] == q[row] || abs(q[row]-q[i])==(row-i)) {
            return 0;
        }
    }
    return 1;
}

/**
 *  回溯放置皇后
 *
 *  @param int toRow - 从toRow行开始穷举地排皇后
 */
void putQueen(int toRow) {
    int i;
    for(i=0; i<max; i++) {
        q[toRow] = i; // 表示将要在第toRow行，第i列放一个皇后
        // 检查刚刚将要放入的那个皇后能否成功放进去
        if(checkValid(toRow)) {
            // 当放置完后，就输出一组解，否则就继续放下一个皇后
            if (toRow == max - 1) {
                show();
                sum++;
            } else {
                putQueen(toRow + 1);
            }
        }
    }
}

int main() {
    printf("请输入皇后的数量：");
    scanf("%d", &max);
    while(max<0 || max==2 || max==3 || max >= 16) {
        if(max < 0) {
            printf("皇后数量不能小于0！");
        } else if (max >= 16) {
            printf("皇后数量应该小于16");
        } else if (max == 2 || max == 3) {
            printf("%d皇后问题无解\n", max);
            exit(0);
        }
        scanf("%d", &max);
    }
    q = (int *)malloc(sizeof(int)*max);
    
    printf("以下是%d皇后的所有解法：\n", max);
    putQueen(0);
    printf("解答完毕，共有 %d 种解法\n", sum);
}