题目描述
给定一个n*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解题思路：
与n皇后类似，2n皇后需要方入黑和白，我们先dfs将黑皇后放入棋盘中，在将白皇后放入棋盘中，并且在每次放入过程中检查我们放入的棋子是否符合规则
if(Math.abs(nl[i]-row)==Math.abs(i-line)) return false;这是对角线筛选的判断，我一开始就难在这问题上，导致答案错误。
代码：
import java.util.Scanner;public class Main {static int an=0;static int[] ns=new int[8];static int[] nl=new int[8];public static void main(String[] args) {Scanner in=new Scanner(System.in);//输入int n= in.nextInt();int[][] num=new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {num[i][j]= in.nextInt();}}boolean[][] useNum=new boolean[n][n];dfs(0,0,useNum,num);System.out.println(an);}public static boolean is2n(int line,int row,int temp,int count,int[][] useNum){//temp 2是黑 3是白//行for (int i = 0; i < count ; i++) {if(useNum[line][i]==temp) return false;//被占有了}//列for (int i = 0; i < count; i++) {if(useNum[i][row]==temp) return false;}//对角线 只对count-1层的进行测试for (int i = 0; i <count; i++) {if(line!=0){if(temp==2){if(useNum[1][0]==2&&useNum[0][1]==2)useNum[1][0]=2;if(Math.abs(nl[i]-row)==Math.abs(i-line)) return false;}else if(temp==3){if(Math.abs(ns[i]-row)==Math.abs(i-line)) return false;}}}return true;}public static void dfs(int countA,int countB,boolean[][] useNum,int[][] num){//截至条件if(countB==num.length){an++;return;}if(countA==useNum.length){for (int j = 0; j < useNum.length; j++) {if(!useNum[countB][j]&&num[countB][j]==1&&is2n(countB,j,3,countB,num)){useNum[countB][j]=true;num[countB][j]=3;ns[countB]=j;dfs(countA,countB+1,useNum,num);ns[countB]=0;useNum[countB][j]=false;num[countB][j]=1;}}}else {//候选节点for (int j = 0; j < useNum.length; j++) {if (!useNum[countA][j] && num[countA][j] == 1 && is2n(countA, j, 2,countA, num)) {useNum[countA][j] = true;num[countA][j] = 2;nl[countA]=j;dfs(countA + 1, countB, useNum, num);nl[countA]=0;useNum[countA][j] = false;num[countA][j] = 1;}}}}
}