Nov 8

重温八皇后问题 不指定

felix021 @ 2009-11-8 13:58 [IT » 程序设计] 评论(3) , 引用(0) , 阅读(7211) | 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;
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
Me999 Email Homepage
2009-11-10 22:06
n皇后
为什么这么多人研究它
今天Vijos比赛第一题MS N皇后!
felix021 回复于 2009-11-11 08:47
闲着无聊。。。
ivan Homepage
2009-11-8 22:05
"经常扯蛋有助于预防蛋疼",嗯,这句俗话说的够俗。zan
sandy
2009-11-8 16:04
你也开始咸蛋了。
这个扯的不算多。。我一扯就扯几万字呢。。
不过扯起n皇后,倒是有点意外。。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]