2021年1月2日

皇后问题求摆放方案数

作者 admin

计算 n*n 棋盘中摆放 n 个皇后的方案数

来源EOJ,ECNU Online Judge

输入格式:第一行有一个整数 k,表示有 k 个 case,接下来 2..k+1 行,每行有一整数,表示 n*n 的棋盘 (0 < n <= 8)。

输出格式:输出共有 k 行,每行有一个整数,即 n*n 的摆放皇后的方案数


代码

声明,该代码本人书写,不排除有错的可能,但大多数时候应该是对的。

思路:判断冲突方法可参考这篇文章

success表示方案数。

思路是每行每行的找。第0行,遍历每一列,如果该列可以放东西则标记为1,继续next(下一行),然后再标记回0,继续下一列。

如果执行到第n行,则是一次成功的方案,success++。

#include<bits/stdc++.h>
using namespace std;
int row[20] {0};
int r_c[40] {0};
int rPLUSc[40] {0};

int success=0;
int n;

void next(int nowrow)
{
    if (nowrow==n)
    {
        success++;
        return;
    }
    for (int col=0; col<n; col++)
    {
        if ( row[col]==0 && r_c[nowrow-col+n]==0 && rPLUSc[nowrow+col]==0)
        {

            row[col]=r_c[nowrow-col+n]=rPLUSc[nowrow+col]=1;
            next(nowrow+1);
            row[col]=r_c[nowrow-col+n]=rPLUSc[nowrow+col]=0;
        }
    }
}

int main()
{
    int ca;
    cin>>ca;
    while(ca--)
    {
        success=0;
        cin>>n;
        for (int p=0; p<20; p++)
            row[p]=0;
        for (int p=0; p<40; p++)
        {
            r_c[p]=0;
            rPLUSc[p] =0;
        }
        next(0);
        cout<<success<<endl;

    }

}