2N皇后

痛定思痛。 2022-08-08 14:39 157阅读 0赞

问题描述

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

输入格式

输入的第一行为一个整数n，表示棋盘的大小。

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

输出格式

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

样例输入

1 1 1 1

样例输出

样例输入

1 0 1 1

1 1 1 1

样例输出

回溯法，类似于N皇后问题：

#include<stdio.h>
    	#include<math.h>
    	#include<stdlib.h>
    	int **a,*b,*c;
    	int sum=0,n;
    	int check(int*x,int t){
    		int i;
    		for(i=1;i<t;i++){
    			if(x[i]==x[t]||abs(i-t)==abs(x[i]-x[t]))
    				return 0;
    		}
    		return 1;
    	}
    	void backtrack(int t){
    		int i;
    		if(t>n){
    			if(t>2*n){
    				sum++;
    			}else{
    				for(i=1;i<=n;i++){
    					if(a[t-n][i]==1&&b[t-n]!=i){
    						c[t-n]=i;
    						if(check(c,t-n))
    							backtrack(t+1);
    					}
    				}
    			}
    		}else{
    			for(i=1;i<=n;i++){
    				if(a[t][i]==1){
    					b[t]=i;
    					if(check(b,t))
    						backtrack(t+1);
    				}
    			}
    		}
    	}
    	int main()
    	{
    		int i,j;
    		scanf("%d",&n);
    		a=(int**)malloc(sizeof(int*)*(n+1));
    		b=(int*)malloc(sizeof(int)*(n+1));
    		c=(int*)malloc(sizeof(int)*(n+1));
    		for(i=0;i<=n;i++){
    			a[i]=(int*)malloc(sizeof(int)*(n+1));
    			b[i]=0;
    			c[i]=0;
    		}
    		for(i=1;i<=n;i++)
    			for(j=1;j<=n;j++)
    				scanf("%d",a[i]+j);
    		backtrack(1);
    		printf("%d\n",sum);
    		return 0;
    	}

![SouthEast][]

![SouthEast 1][]

[SouthEast]: /images/20220805/b4973ff831754327b795801c0a85a703.png
[SouthEast 1]: /images/20220805/a688041ef16e4f6689f654341d609859.png