首页
社区
课程
招聘
[求助][已解决(细心是硬道理)]内嵌汇编代码求解17皇后问题时计算异常的问题
发表于: 2007-10-11 21:26 6042

[求助][已解决(细心是硬道理)]内嵌汇编代码求解17皇后问题时计算异常的问题

2007-10-11 21:26
6042
今天写一个n皇后问题的程序,在网上down了一个C函数,可以算32皇后以内问题。不过我用VC6编译运行后,发现速度太慢了,算16皇后居然要70多秒(CPU P4 1.8GHz,RAM 512M),估计是大量对内存读写的缘故。我重写了一段内嵌的汇编代码来替代这个C函数,主要使用寄存器运算,算16皇后只需要22秒。

可是问题来了,1-16皇后都能正确计算,可是算17皇后,居然22秒后就说无解!而我换用那个C函数来算,虽然用了500多秒,但是计算出了正确结果。

下面是我的代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

unsigned long sum=0,upperlim=1,n=17;
/*
void test(unsigned long row, unsigned long ld, unsigned long rd)
{//row eax, ld ebx, rd edx, pos ecx, p edi, upperlim ebp
        if(row!=upperlim)
        {
                long pos=upperlim&(~(row|ld|rd));
                long p;

                while(pos)
                {
                        p=pos&(-pos);
                       
                        pos-=p;
                       
                        test(row+p,(ld+p)<<1,(rd+p)>>1);
                }
        }
        else sum++;
}   
*/

int main(int argc,char *argv[])
{
        time_t tm;
        int if2n;
       
        if(argc!=1)n=atoi(argv[1]);
       
        if((n<1)||(n>32))return printf("只能计算1-32之间\n");
       
        printf("%d皇后\n",n);

        if2n=!(n%2);
       
        upperlim=(upperlim<<n)-1;

        _sleep(1000);

        tm=time(0);

        _asm
        {
                pushad
                pushfd
                mov ebp,upperlim
                xor eax,eax
                xor ebx,ebx
                xor edx,edx
                call _test
                jmp _over_
_test:
                cmp eax,ebp                                //if(row!=upperlim)
                jz _test_get_

                mov ecx,eax                                //long pos=upperlim&(~(row|ld|rd));
                or ecx,ebx
                or ecx,edx
                not ecx
                and ecx,ebp
_test_while_:
                jcxz _test_ret_                        //while(pos)

                mov edi,ecx                                //p=pos&(-pos);
                neg edi
                and edi,ecx

                sub ecx,edi                                //pos-=p;

                push eax
                push ecx
                push edx
                push ebx
                push edi

                add eax,edi

                add ebx,edi
                shl ebx,1

                add edx,edi
                shr edx,1

                call _test                                //test(row+p,(ld+p)<<1,(rd+p)>>1);

                pop edi
                pop ebx
                pop edx
                pop ecx
                pop eax

                jmp _test_while_

_test_get_:
                inc sum                                        //sum++;

_test_ret_:
                ret
_over_:
                popfd
                popad
        };

       
//        test(0,0,0);       
        printf("共有%ld种排列,计算时间%d秒\n",sum,(int)(time(0)-tm));

        return 0;
}

其中用绿色标记的被我注释掉的就是网上down的那个C代码,而用蓝色标记的就是我写的汇编代码。可以分别注释掉两者中的任何一个来检测两者的运行情况。

我的代码可以正确求解1-16皇后问题,可是就是偏偏求解17皇后的时候出错。我分析了一下午,IDA呀OllyICE呀都上了,就是找不出我的代码和down的C函数到底有什么致命区别,会导致17皇后的计算错误。

请各位高手帮忙分析调试一下,望不吝赐教,十分感谢!!

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (7)
雪    币: 235
活跃值: (17)
能力值: ( LV9,RANK:170 )
在线值:
发帖
回帖
粉丝
2
我认为这似乎不是VC6编译器的问题,因为我把我的汇编代码拿到Masm32下ml的结果和之前是完全一样的。
2007-10-11 22:15
0
雪    币: 105
活跃值: (10)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
3

    jcxz _test_ret_      //while(pos)
改为
  jecxz _test_ret_      //while(pos)
即可
你是判定了CX而不是ECX,故无解
2007-10-12 13:42
0
雪    币: 325
活跃值: (97)
能力值: ( LV13,RANK:530 )
在线值:
发帖
回帖
粉丝
4
int main(int argc, char *argv[])
{
        time_t tm;
        int n = 16;

        if (argc != 1)
                n = atoi(argv[1]);
        tm = time(0);

        // 因为整型数的限制,最大只能32位,
        // 如果想处理N大于32的皇后问题,需要
        // 用bitset数据结构进行存储。
        if ((n < 1) || (n > 32))                  
        {
                printf(" 只能计算1-32之间\n");
                exit(-1);
        }
       
        printf("%d 皇后\n", n);

       
        /*// N个皇后只需N位存储,N列中某列有皇后则对应bit置1。
        upperlim = (upperlim << n) - 1;      
       

        test(0, 0, 0);*/
       
        __asm
        {
        mov        esi, upperlim                ; upperlim
        mov        ecx, n
        shl        esi, cl
        add        esp, 8
        sub        esi, 1
        mov        upperlim, esi                ; upperlim

; 71   :        
; 72   :
; 73   :         test(0, 0, 0);

        je        SHORT $LN11_main
        test        esi, esi
        je        SHORT $LN8_main
        lea ecx,[ecx]
$LL10_main:
        mov        ecx, esi
        neg        ecx
        and        ecx, esi
        mov        eax, ecx
        sar        eax, 1
        push        eax
        lea        edx, DWORD PTR [ecx+ecx]
        sub        esi, ecx
        call        _test_                        ; test
        jmp $LN10_main
        _test_:
; _row$ = ecx
; _ld$ = edx
; _rd$ = 8                                                ; size = 4

; 12   :         if (row != upperlim)

        mov        eax, DWORD PTR upperlim                ; upperlim
        push        ebx
        push        edi
        mov        edi, ecx
        cmp        edi, eax
        mov        ebx, edx
        je        SHORT $LN4_test
        push        ebp
        mov        ebp, DWORD PTR 8[esp+8]
        push        esi
        mov        esi, edi
        or        esi, ebx
        or        esi, ebp
        not        esi
        and        esi, eax
        je        SHORT $LN9_test
$LL3_test:
        mov        eax, esi
        neg        eax
        and        eax, esi
        lea        ecx, DWORD PTR [eax+ebp]
        sar        ecx, 1
        lea        edx, DWORD PTR [eax+ebx]
        push        ecx
        add        edx, edx
        lea        ecx, DWORD PTR [eax+edi]
        sub        esi, eax
        call        _test_                        ; test
        test        esi, esi
        jne        SHORT $LL3_test
$LN9_test:
        pop        esi
        pop        ebp
        pop        edi
        pop        ebx

        ret        4
$LN4_test:
        add        DWORD PTR sum, 1                        ; sum
        pop        edi
        pop        ebx
        ret        4
$LN10_main:
        test        esi, esi
        jne        SHORT $LL10_main
        jmp        SHORT $LN8_main
$LN11_main:
        add        DWORD PTR sum, 1                        ; sum
$LN8_main:
        }
        printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int) (time(0) - tm));
}

17 皇后
共有95815104种排列, 计算时间95秒
请按任意键继续. . .

其实还没有VC++ 自己编译的代码快
2007-10-12 14:05
0
雪    币: 235
活跃值: (17)
能力值: ( LV9,RANK:170 )
在线值:
发帖
回帖
粉丝
5
正解!确实如此。其实我一般不怎么用jcxz(jecxz)这个指令的,这次突然想起来就用了,结果16位编程思维定势埋下了一个定时炸弹亚,呵呵。很佩服你的细心,当然,也很可能你是从16到17这个变化分析出来可能的出错位置,然后重点关注的。不过自己写的代码硬要找bug确实很难——思维定势。所以大家一起讨论才是王道。

我贴的代码是为了便于分析的原始代码,我本来在逐位搜索的基础上加入左右对称的优化,只搜索一半,所以时间也节省一半。寄存器到用时方恨少,本来很多经常使用的常量我都打算用寄存器保存的,不过就eax,ecx,edx,ebx,ebp,edi,esi这么几个能用,只好忍了。

下面贴出我的最终代码,搜索17皇后共79秒,比楼上快一些哦,呵呵(ThinkPad T43 CPU P41.86GHz RAM 512M)

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

unsigned long sum=0,sumx=0,upperlim=1,n=17;

int main(int argc,char *argv[])
{
        time_t tm;
        int if2n;
       
        if(argc!=1)n=atoi(argv[1]);
       
        if((n<1)||(n>32))return printf("只能计算1-32之间\n");
       
        printf("%d皇后\n",n);

        if2n=!(n%2);
       
        upperlim=(upperlim<<n)-1;

        _sleep(1000);

        tm=time(0);

        _asm
        {
                pushad
                pushfd
                mov ebp,upperlim
                ror n,1
                xor eax,eax
                xor ebx,ebx
                xor edx,edx
                xor esi,esi
                call _test
                jmp _over_
_test:
                inc esi
                cmp esi,2
                jnz _test_begin_
                test n,7fffffffh
                jnz _test_dec_
                rol n,1
                jnc _test_ret_
                mov edi,sum
                mov sumx,edi
_test_dec_:
                dec n
_test_begin_:
                cmp eax,ebp                                //if(row!=upperlim)
                jz _test_get_

                mov ecx,eax                                //long pos=upperlim&(~(row|ld|rd));
                or ecx,ebx
                or ecx,edx
                not ecx
                and ecx,ebp
_test_while_:
                jecxz _test_ret_                        //while(pos)

                mov edi,ecx                                //p=pos&(-pos);
                neg edi
                and edi,ecx

                sub ecx,edi                                //pos-=p;

                push eax
                push ecx
                push edx
                push ebx
                push edi

                add eax,edi

                add ebx,edi
                shl ebx,1

                add edx,edi
                shr edx,1

                call _test                                //test(row+p,(ld+p)<<1,(rd+p)>>1);

                pop edi
                pop ebx
                pop edx
                pop ecx
                pop eax

                jmp _test_while_

_test_get_:
                inc sum                                        //sum++;

_test_ret_:
                dec esi
                ret
_over_:
                popfd
                popad
        };

        if(if2n)sumx=sum;
       
        printf("共有%ld种排列,计算时间%d秒\n",sum+sumx,(int)(time(0)-tm));

        return 0;
}
2007-10-12 21:52
0
雪    币: 107
活跃值: (11)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
6
T43是PM的CPU吧
2007-10-12 23:52
0
雪    币: 235
活跃值: (17)
能力值: ( LV9,RANK:170 )
在线值:
发帖
回帖
粉丝
7
是的,不过我都习惯叫P4。
2007-10-13 11:14
0
雪    币: 222
活跃值: (10)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
8
不错,支持一下吧
2007-10-13 15:14
0
游客
登录 | 注册 方可回帖
返回
//