OpenJudge1700:八皇后问题 //不属于基本法的基本玩意

1700:八皇后问题//搜索


总时间限制:: 10000ms

内存限制:: 65536kB

描述

在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

输入

无输入。

输出

按给定顺序和格式输出所有八皇后问题的解（见Sample Output）。

样例输入

无

样例输出

No. 1

1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

No. 2

1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0

No. 3

1 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0

0 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0

No. 4

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

No. 5

0 0 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 1

0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0

No. 6

0 0 0 1 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0

No. 7

0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1

0 0 0 1 0 0 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0

No. 8

0 0 1 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

No. 9

0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0

...以下省略

提示

此题可使用函数递归调用的方法求解。

来源

计算概论05

分析:

这道题就是经典的递归回溯法.但是我WA了好多次 ,就是因为这个输出.特别的恶心.反人类的输出.还得把整个棋盘翻转一下输出.简直了.这点真的特别坑.反正很恶心.

放出代码,这个没什么的吧.

#include<cstdio>

int map_1[9][9];

int xie_1[9][9]={

    0,0,0,0,0,0,0,0,0,

    0,1,9,10,11,12,13,14,15,

    0,2,1,9,10,11,12,13,14,

    0,3,2,1,9,10,11,12,13,

    0,4,3,2,1,9,10,11,12,

    0,5,4,3,2,1,9,10,11,

    0,6,5,4,3,2,1,9,10,

    0,7,6,5,4,3,2,1,9,

    0,8,7,6,5,4,3,2,1,

};

int xie_2[9][9]={

    0,0,0,0,0,0,0,0,0,

    0,1,2,3,4,5,6,7,8,

    0,2,3,4,5,6,7,8,9,

    0,3,4,5,6,7,8,9,10,

    0,4,5,6,7,8,9,10,11,

    0,5,6,7,8,9,10,11,12,

    0,6,7,8,9,10,11,12,13,

    0,7,8,9,10,11,12,13,14,

    0,8,9,10,11,12,13,14,15,

};

int xie1[20],xie2[20],heng[9],lie[9],cnt ;

int out(){

    cnt++;

    printf("No. %d\n",cnt);

    for(int i=1;i<=8;i++){

    for(int j=1;j<=8;j++){

        printf("%d ",map_1[j][i]);

    }

    printf("\n");

    }

    return 0;

}

int dfs(int x)

{

    if(x>8){

    out();

    return 0;

    }

    for(int i=1;i<=8;++i)

    {

    if(!xie1[xie_1[x][i]]&&!xie2[xie_2[x][i]]&&!heng[x]&&!lie[i])

    {

        xie1[xie_1 [x][i]]=1;

        xie2[xie_2 [x][i]]=1;

        heng[x]=1;

        lie [i]=1;

        map_1 [x][i]=1;

        dfs(x+1);

        xie1[xie_1[x][i]]=0;

        xie2[xie_2[x][i]]=0;

        heng[x]=0;

        lie[i]=0;

        map_1[x][i]=0;

         }

    }

    return 0;

}

int main()

{

    dfs(1);

    return 0;

}

巴特西

OpenJudge1700:八皇后问题 //不属于基本法的基本玩意

1700:八皇后问题//搜索

最新文章

热门文章