愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

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);
}