八皇后问题 2n皇后问题

时间：2023-03-09 00:25:25
八皇后问题 2n皇后问题

Description

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

Input

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

Output

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

Sample Input





Sample Output










 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <sstream>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 #define Bug cout<<"---------------------"<<endl

 const int maxn=1e5+;

 using namespace std;

 int vis[];

 int A[];

 int ans[][];

 int cnt=;

 int judge(int n)

 {

     int flag=;

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

     {

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

         {

             if(i!=j&&abs(i-j)==abs(A[i]-A[j]))  //别忘了i!=j

                 flag=;

         }

     }

     return flag;

 }

 void dfs(int p,int n)

 {

     A[n]=p;

     if(judge(n)==)

         return ;

     if(n==)

     {

         cnt++;

         for(int k=;k<=;k++)

             ans[cnt][k]=A[k];  //第一次写成ans[++cnt][k]=A[k]了。。。

         return ;

     }

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

     {

         if(vis[i]==)

         {

             vis[i]=;

             dfs(i,n+);

             vis[i]=;

         }

     }

 }

 int main()

 {

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

     {

         vis[i]=;

         dfs(i,);

         vis[i]=;

     }

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int n;

         scanf("%d",&n);

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

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

         printf("\n");

     }

     return ;

 }




相似问题：


八皇后问题 2n皇后问题


样例输入：








样例输出：








换了种写法，用列、主对角线和副对角线来判断




#include <stdio.h>

#include <string.h>

#include <iostream>

#include <string>

#include <math.h>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <sstream>

const int INF=0x3f3f3f3f;

typedef long long LL;

const int mod=1e9+;

const double PI = acos(-);

#define Bug cout<<"---------------------"<<endl

const int maxn=1e4+;

using namespace std;

int G[][];

int jm[][];

int ans;

void DFS(int num,int sum)

{

    if(num>)

    {

        ans=max(ans,sum);

        return;

    }

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

    {

        if(jm[][i]==&&jm[][num-i+]==&&jm[][num+i]==)

        {

            jm[][i]=jm[][num-i+]=jm[][num+i]=;

            DFS(num+,sum+G[i][num]);

            jm[][i]=jm[][num-i+]=jm[][num+i]=;

        }

    }

}

int main()

{

    #ifdef DEBUG

    freopen("sample.txt","r",stdin);

    #endif

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

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

    {

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

        {

            scanf("%d",&G[i][j]);

        }

    }

    DFS(,);

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

    return ;

}






Description


　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。






Input


　　输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。






Output


　　输出一个整数，表示总共有多少种放法。






Sample Input








4

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1












Sample Output








2












 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <sstream>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 #define Bug cout<<"---------------------"<<endl

 const int maxn=1e5+;

 using namespace std;

 int G[][];

 int vis[];

 int tem[];

 int ans[][];

 int cnt;

 int judge(int step,int n)

 {

     for(int i=;i<=step;i++)

     {

         for(int j=;j<=step;j++)

         {

             if(i!=j&&abs(i-j)==abs(tem[i]-tem[j]))

                 return ;

         }

     }

     return ;

 }

 void DFS(int step,int n)

 {

     if(judge(step,n)==)

         return ;

     if(step==n)

     {

         cnt++;

         for(int k=;k<=n;k++)

             ans[cnt][k]=tem[k];

         return ;

     }

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

     {

         if(!vis[i]&&G[step+][i])

         {

             vis[i]=;

             tem[step+]=i;

             DFS(step+,n);

             vis[i]=;

         }

     }

 }

 void Solve(int n)

 {

     int num=;

     for(int i=;i<=cnt;i++)

     {

         for(int j=i+;j<=cnt;j++)

         {

             int k;

             for(k=;k<=n;k++)

             {

                 if(ans[i][k]==ans[j][k])

                     break;

             }

             if(k>n)

                 num++;

         }

     }

     printf("%d\n",num*);

 }

 int main()

 {

     int n;

     scanf("%d",&n);

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

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

             scanf("%d",&G[i][j]);

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

     {

         if(G[][i])

         {

             vis[i]=;

             tem[]=i;

             DFS(,n);

             vis[i]=;

         }

     }

     Solve(n);

     return ;

 }


相关文章