问题描述

给定一个n*n的棋盘，棋盘上有一些不能放置皇后的位置。现在把n个黑皇后和n个白皇后放到棋盘上，让任意两个黑皇后不在同一行、列或对角线上，任意两个白皇后不在同一行、列或对角线上。玩法有多少种？n小于或等于8。

输入格式

输入的行是整数n，表示棋盘的大小。

接下来的n行，每行包含n个0或1的整数。如果一个整数是1，说明对应的位置可以放一个皇后；如果一个整数是0，这意味着相应的位置不能放皇后。

输出格式

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

样本值输入

四

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

抽样输出

2

样本值输入

四

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1

抽样输出

0

导入Java . util . scanner；

公共类queens问题{

static int a[]，s[]；

static int arr[][]；

静态int n；

static int AC=0；

静态int q；

公共静态void main(String[] args) {

//

扫描仪sc=新扫描仪(system . in)；

n=sc . Nextint()；

a=new int[n]；

s=new int[n]；

arr=new int[n 1][n 1]；

for(int I=1；I=n；I)

for(int j=1；j=n；j)

arr[I][j]=sc . Nextint()；

sc . close()；

//先放黑皇后

pa(0)；

system . out . println(q)；

}

public static void pa(int m) {

if(m==n ) {

//放一个黑皇后，再放一个白皇后

pas(0)；

返回；

}

for(int I=1；I=n；i ) {

//如果是1，可以放皇后

if(arr[ m 1 ][ i ]！=0) {

a[m]=I；//放入一个皇后

AC=1；//1表示没有冲突

for(int j=0；j m；j ) {

//同行和列之间有冲突吗

if(a[ m ]==a[ j ])

AC=0；

//对角线上有冲突吗

else if(Math . ABS(a[j]-a[m])==(m-j))

AC=0；

}

if(ac==1)

pa(m1)；

}

}

}

public static void pas(int m) {

if(m==n ) {

q；

返回；

}

for(int I=1；I=n；i ) {

if(arr[ m 1 ][ i ]==1 a[ m ]！=i) {

s[m]=I；

AC=1；

for(int j=0；j m；j ) {

if(s[ m ]==s[ j ])

AC=0；

else if(Math . ABS(s[j]-s[m])==(m-j))

AC=0；

}

if(ac==1)

pas(m1)；

}

}

}

}