【5001】n皇后问题

Time Limit: 10 second

Memory Limit: 2 MB

在n*n的棋盘上放置n个皇后（国际象棋中的皇后，n≤10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求出所有的摆放方法

Input

输入文件仅一行，输入n(0≤n≤10)。

Output

每行输出一种方案，每种方案按顺序输出皇后所在的列号，各个数之间用空格隔开，若无方案，则输出“No solution!”。（最后用换行结束）

Sample Input

Sample Output

2 4 1 3

3 1 4 2

【题解】

这题的主要问题在于，要如何判断当前搜素到的位置能不能放下棋子。

这里用了3个数组来解决问题。

zxbo,fxbo,bo;

zxbo数组和fxbo数组代表①类。

bo数组代表②类。

用b[i][j],a[i][j]两个二维数组存储每个位置所代表的类。

其中b[i][j] = i - j;a[i][j] = i + j;

如n = 5 得到的b数组和a数组如下。

可以看到b数组从左上到右下的对角线，数字是一样的。

而a数组从右上到左下的对角线，数字也是一样的。

我们用fxbo,zxbo分别表示负数和正数的b数组中的数字是否出现过。

用bo数组表示a数组中的数字是否出现过。（a数组不会出现负数）

然后每次放棋子的时候我们只要看看a[i][j]和b[i][j]的值 m,n。然后看看bo[m] 和 fxbo[n]或zxbo[n] 是否为false，如果为false则表示可以放，否则不能放。

放完后把上面的bo,fxbo或 zxbo数组置为true;

一行一行的搜索就好，同时还应该加入一个lbo数组，用来判断列的重复情况。

【代码】

#include <cstdio>

int a[12][12],b[12][12],n,ans[20],nn = 0; //ans 数组用于记录答案，nn整形用于判断答案数，以此来判断是否输出无解信息。

bool zxbo[25],fxbo[25],lbo[12],bo[25];

void init()

{

    scanf("%d",&n);

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

        for (int j = 1; j <= n;j++)

            a[i][j] = i + j,b[i][j] = i - j; //初始化a,b数组

    for (int i = 1;i <= n;i++) //初始化各个判重数组

        lbo[i] = false;

    for (int i = 0;i <= 22;i++)

        zxbo[i] = false,fxbo[i] = false,bo[i] = false;

}

void output_ans() //放完所有的棋子，然后输出答案。

{

    for (int j = 1;j <= n-1;j++)

        printf("%d ",ans[j]);

    printf("%d\n",ans[n]);

}

void sear_ch(int x ) //搜索第x行

{

    if (x == n+1) //如果已经搜完了，就输出答案。

        {

            output_ans();

            nn++;

            return;

        }

    for (int i = 1; i <= n;i++) //尝试每一列

        {

            if (lbo[i]) continue; //如果已经搜索过这一列，就搜下一列。

            int tt = a[x][i],t = b[x][i]; //获取这个位置的“两个类的值”

            bool flag = true; //用来判断两个对角线是否都符合要求。

            flag = bo[tt];

            if (flag) continue;

            if ( t > 0)

                flag = zxbo[t];

                    else

                        flag = fxbo[-t];

            if (flag) continue;

            bo[tt] = true; //tt = i + j 是一定大于0的

            if (t > 0) //而t = i - j 是可能小于0 的

                zxbo[t] = true;

                    else

                        fxbo[-t] = true;

            lbo[i] = true; //标记这一列被占领

            ans[x] = i; //记录答案

            sear_ch(x+1); //寻找下一行.

            lbo[i] = false;

            bo[tt] = false;

            if (t > 0)

                zxbo[t] = false;

                    else

                        fxbo[-t] = false;

        }

}

void s_p()

{

    if (nn == 0)

        printf("No solution!\n");

}

int main()

{

    init();

    sear_ch(1);

    s_p();

    return 0;

}

巴特西

【5001】n皇后问题

Input

Output

Sample Input

Sample Output

最新文章

热门文章