n皇后问题_牛客博客

一.普通的n皇后问题
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个皇后，使任意的两个皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
输出格式
输出放皇后的情况，0表示不放，1表示放，行末换行
　　输出一个整数，表示总共有多少种放法。
样例输入
4
样例输出
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

#include<stdio.h>
int count=0;
void Queen(int n,int l);
void Queen1(int n,int l);
bool CanPut(int i,int j,int (*a)[8],int n);
bool CanPut1(int i,int j,int (*a)[8],int n);
void Print(int (*a)[8],int n);
int a[8][8];
int main()
{
    int n;
    scanf("%d",&n);
    Queen(n,0);
    if(count)
        printf("%d\n",count);
    else
        printf("0\n");

    return 0;
}
void Queen(int n,int l){
         if(l==n){
             count++; 
             int i,j;
             for(i=0;i<n;i++){
              for(j=0;j<n;j++)
                 printf("%d ",a[i][j]);
                 printf("\n");
             }
             printf("\n");
         } 

         else{ 
                for(int j=0;j<n;j++){
                            a[l][j]=1;//1表示放入 
                            if(CanPut(l,j,a,n))
                              Queen(n,l+1);
                            a[l][j]=0;//不合适，往前回溯，变成0 
                }
         }
}
bool CanPut(int i,int j,int (*a)[8],int n){
          int k,s=0;
          for(k=i-1;k>=0;k--){
                    s++;
                    if(a[k][j]==1||a[k][j-s]==1||a[k][j+s]==1)//同列或者处于对角线上 
                    return false;
          }
          return true;
}

二.改编n皇后
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个皇后，使任意的两个皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
　　输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2

#include<iostream>
#include<cmath>
using namespace std;
int count=0,n;
int a[8][8],pb[10];
bool Checkb(int row,int pb[]){
          for(int k=0;k<row;k++){
                    if(pb[k]==pb[row]||abs(pb[row]-pb[k])==row-k)//同行或者处于对角线 
                    return false;
          }
          return true;
}
void Queen(int row){
         if(row==n)
             count++;
         else{ 
                for(int j=0;j<n;j++){
                     if(a[row][j]==0) continue;//位置不能占用 
                            pb[row]=j;//记录棋子在当前行的位置 
                            if(Checkb(row,pb))//检测棋子位置是否合法 
                              Queen(row+1);//判断下一行 
                }
         }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
          cin>>a[i][j];
    Queen(0);
    if(count)
        cout<<count<<endl;
    else
        cout<<0<<endl;

    return 0;
}
2.另一种在原来的数组上改动的回溯法
#include<stdio.h>
int count=0;
void Queen(int n,int l);
void Queen1(int n,int l);
bool CanPut(int i,int j,int (*a)[8],int n);
bool CanPut1(int i,int j,int (*a)[8],int n);
void Print(int (*a)[8],int n);
int a[8][8];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
          scanf("%d",&a[i][j]);
    Queen(n,0);
    if(count)
        printf("%d\n",count);
    else
        printf("0\n");

    return 0;
}
void Queen(int n,int l){
         if(l==n)
             count++; 
         else{ 
                for(int j=0;j<n;j++){
                     if(a[l][j]==0) continue;
                            a[l][j]=2;
                            if(CanPut(l,j,a,n))
                              Queen(n,l+1);
                            a[l][j]=1;
                }
         }
}
bool CanPut(int i,int j,int (*a)[8],int n){
          int k,s=0;
          for(k=i-1;k>=0;k--){
                    s++;
                    if(a[k][j]==2||a[k][j-s]==2||a[k][j+s]==2)
                    return false;
          }
          return true;
}

2n皇后问题
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
　　给定一个nn的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
*输入格式**
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
　　输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
int count=0;
int a[20][20],n;
int pb[20],pw[20]; //记录shu
bool Checkb(int row,int pb[]){
          for(int k=0;k<row;k++){
                    if(pb[k]==pb[row]||abs(pb[row]-pb[k])==row-k)
                    return false;
          }
          return true;
}
bool Checkw(int row,int pw[]){
          for(int k=0;k<row;k++){
                    if(pw[k]==pw[row]||abs(pw[row]-pw[k])==row-k)
                    return false;
          }
          return true;
}
void Queen1(int row){
         if(row==n)
             count++; //黑白都排完才算一次
         else{
                for(int j=0;j<n;j++){
                     if(a[row][j]==0||pb[row]==j)  continue;
                            pw[row]=j;
                            if(Checkw(row,pw))
                              Queen1(row+1);
                }
         }
}
void Queen(int row){
         if(row==n)
             Queen1(0);
         else{ 
                for(int j=0;j<n;j++){
                     if(a[row][j]==0) continue;
                            pb[row]=j;
                            if(Checkb(row,pb))
                              Queen(row+1);
                }
         }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
          scanf("%d",&a[i][j]);
    Queen(0);
    if(count)
        printf("%d\n",count);
    else
        printf("0\n");

    return 0;
}