重温八皇后问题

Kruskal贪心算法求最小生成树

数据结构：栈

Nov 8

felix021 @ 2009-11-8 13:58 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(7579) | Via 本站原创

大 | 中 | 小

    如果从大一算起，写C已经有3年了。其实高中也写过，但是基本可以忽略不计。代码量，比起acm/icpc正规军来说，当然还是少得多；但是应该也有几万行了。写了这么多代码，也看了不少算法，感觉就是，这样的经验需要时间的积淀。曾经觉得很难的问题，现在已经在脑子里豁然开朗。就比如八皇后问题，上一次研究它，是2007年6月的事情。那会儿应该能想的清楚了，但是对于那时候的我而言，回溯算法仍然是比较难以理解的（记得有一次想写一个生成全排列的程序，写了半天都不对，最后还是让sandy写了一个标程抄了两遍，才逐渐理解）。差不多2年半过去了，再回首这个八皇后，发现思路非常清晰，很快就把代码写出来了。

    废话完回到这个问题上。它的两个难点在于：1. 如何判断某一个位置是否可以放置一个皇后；2. 回溯。

    如果给这个8*8的矩阵上个坐标，横向(rows)为i = 0 to 7，纵向(columns)为j = 0 to 7。那么可以发现，在每一条斜线(/)方向上，每一个格子的横纵坐标之和(i + j)是一个固定值，从左上到右下的斜线，其值依次是0~14 (0+0; 0+1,1+0; 0+2,1+1,2+0; ... ; 6+7,7+6; 7+7)。同样地，，在每一条反斜线(\)方向上，每一个格子的横坐标与纵坐标的关系是， (i + (7 - j))是固定值，从右上到左下的斜线，其值依次是0~14。

    因此，在开始寻找方案之前，给横、纵、斜线、反斜线方向各设置一个数组，所有元素初始化为0（表示可以放置），那么，在将皇后放置到(i, j)之前检查rows[i]、cols[j]、slash[i+j]、bslash[i+7-j]是否都为0，就可以判断这个位置能否放置皇后。由于放置的过程是从上到下一行一行放的，所以这个rows数组实际上可以去掉。这样第一个难点就解决了。（p.s. bslash -> backslash）

    第二个难点，回溯，这个我觉得不是很容易能说清楚的。简单地说，需要回溯的就是前面提到的cols/slash/bslash数组。一行一行地来：每一行从第一个位置开始查找，当找到一个有效位置，放置一个皇后，将对应的值置为1（以后的位置就可以检测是否可放），然后继续查找下一行的位置（递归调用）；如果下一行没有合适的位置（递归返回），将对应的位置重置为0，然后查找这一行下一个位置。

    这个问题实在不是一个有难度的问题，我居然扯了这么多。可见我现在多闲啊。俗话说的好：经常扯蛋有助于预防蛋疼。

    下附代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8

int count;
int rows[N],    cols[N],    slash[2 * N - 1], bslash[2 * N - 1];
//每行放的位置，纵向不可放，斜向不可放（/），斜向不可放(\)

void place(int i) {
    int j;
    for (j = 0; j < N; ++j) {
        if (cols[j] == 0 && slash[i + j] == 0 && bslash[i + (N-1) - j] == 0) {
            rows[i] = j;

            cols[j] = 1;
            slash[i + j] = 1;
            bslash[i + (N-1) - j] = 1;

            if (i == N - 1) {
                /*
                int k;
                for (k = 0; k < N; ++k) {
                    printf("%d ", rows[k]);
                }
                printf("\n");
                */
                count++;
            }
            else {
                place(i + 1);
            }

            //回溯
            cols[j] = 0;
            slash[i + j] = 0;
            bslash[i + (N-1) - j] = 0;
        }
    }
}

int main () {

    memset(rows, 0, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    memset(slash, 0, sizeof(slash));
    memset(bslash, 0, sizeof(bslash));

    count = 0;
    place(0);
    printf("count = %d\n", count);
    return 0;
}

欢迎扫码关注：