问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
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
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
1 import java.math.BigInteger;
2 import java.util.Arrays;
3 import java.util.Scanner;
4
5
6 public class Main {
7 static int sum;
8 static int n;
9 //检测红皇后当前可不可放置的参数
10 static int[] lie;
11 static int[] leftup;//检测左上对角线
12 static int[] leftdown;//检测坐下对角线
13 //检测白皇后当前可不可放置的参数
14 static int[] lie1;
15 static int[] leftup1;
16 static int[] leftdown1;
17 static int[][] a;
18 public static void main(String[] args) {
19 Scanner input = new Scanner(System.in);
20 n = input.nextInt();
21 a = new int[n+1][n+1];
22 for(int i=1;i<=n;i++){
23 for(int j=1;j<=n;j++){
24 a[i][j] = input.nextInt();
25 }
26 }
27 lie = new int[n+1];
28 leftup = new int[2*n];
29 leftdown = new int[2*n];
30 lie1 = new int[n+1];
31 leftup1 = new int[2*n];
32 leftdown1 = new int[2*n];
33 f(1);
34 System.out.println(sum);
35 }
36 public static void f(int i){
37 if(i>n) sum++;//找到一种加1
38 else{
39 for(int j=1;j<=n;j++){
40 //可不可以放置红皇后
41 if(lie[j]!=1&&leftup[i+j-1]!=1&&leftdown[i-j+n]!=1&&a[i][j]!=0){
42 //放置红皇后后放置白皇后
43 for(int h=1;h<=n;h++){
44 //可不可防止白皇后，h!=j表示红皇后放置的地方不可以放置红皇后
45 if(lie1[h]!=1&&leftup1[i+h-1]!=1&&leftdown1[i-h+n]!=1&&h!=j&&a[i][h]!=0){
46 //记下放置了的位置让相应检测位置1
47 lie[j] = 1;
48 leftup[i+j-1] = 1;
49 leftdown[i-j+n] = 1;
50 lie1[h] = 1;
51 leftup1[i+h-1] = 1;
52 leftdown1[i-h+n] = 1;
53 f(i+1);
54 //回溯，相应检测为置0
55 lie[j] = 0;
56 leftup[i+j-1] = 0;
57 leftdown[i-j+n] = 0;
58 lie1[h] = 0;
59 leftup1[i+h-1] = 0;
60 leftdown1[i-h+n] = 0;
61 }
62 }
63 }
64 }
65 }
66 }
67 }