问题描述
给定一个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<8的n*n的棋盘上放两个颜色的皇后，同一行或列、同一斜线上不能有同一种颜色的皇后。跟经典的八皇后问题类似，我们可以用递归或者回溯。
题目中的实例讲的很明白，我就不多重复了。我们做这样的算法题，主要目的就是让程序按照相应的步骤来执行，所以说我们只需要按照他给定的思路一步步的写下去即可。
首先，我们需要定义两个全局变量，一个是用来存储棋盘的二维数组，一个是记录有多少种方法的answer
我们假设黑皇后用2表示，白的用3表示，下面就是遍历棋盘，符合条件的标注为相应的数字。
- 这里有这样几个难点：首先，我们需要怎样遍历才能完美的判断出皇后的位置？其次，判断是否符合条件时我们的思路以及相应的程序是怎样的？
- 第一个问题：
我上面提到了，我们在这里用到的是回溯和递归，我们定义的这个方法需要传两个参数，第一个是n，也就是从第n行开始，第二个是d，也就是皇后的颜色，在这里d只能取2和3。
我们初次调用此方法是先放黑皇后，d一开始等于2，进来之后是个for循环，先假设第一个没有棋子的地方符合，标记之后判断是否符合，如果符合，进入下一行，如果不符合，取消标记，并继续循环查看本行的下一个位置。
- 注意，如果符合，我们要递归调用本方法而不是继续循环；如果不符合我们需要取消标记并继续循环，不要混了。不符合的情况用到了回溯，符合以及后面的一个情况用到了递归。
检查完黑皇后之后，我们让d变成3继续上面的操作，符合相应的条件后便退出程序显示结果，我相信大家应该可以看明白这些地方。
- 第二个问题：
判断是否符合条件，这里需要特别注意设定的边界值，防止数组角标越界。
- 我们需要特别判断同一列，左斜上方，右斜上方。斜下方就不需要了，因为我们放棋子是从上往下放的，下面是不可能有的。
每一次判断的依据就是这一行或列是否有与这个位置相同的数字。用三个for循环分别实现这个功能即可。
代码：
import java.util.Scanner; public class NdfsExer { static int[][] arr; static int ans = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // if(n > 8) { // return; // } arr = new int[n][n]; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { arr[i][j] = sc.nextInt(); } } //黑皇后用2表示，白皇后用3表示 dfs(0,2); System.out.println(ans); } private static void dfs(int n, int d) { if(n == arr.length) {//判断一种皇后是否已遍历完成 if(d == 3) { ans++;//说明黑白都看完了，ans++ } dfs(0,3);//递归遍历白皇后 return; } for(int i = 0;i < arr.length;i++) { if(arr[n][i] == 1 && arr[n][i] != 2) { arr[n][i] = d; if(check(n,i)) { dfs(n + 1,d);//本行结束，递归进入下一行 } arr[n][i] = 1;//回溯 } } } private static boolean check(int x, int y) { //判断是否在同一列 for(int i = 0;i < x;i++) { if(arr[i][y] == arr[x][y]) { return false; } } //判断左斜上方 for(int i = x-1,j = y-1;i >= 0 && j >= 0;i--,j--) { if(arr[i][j] == arr[x][y]) { return false; } } //判断右斜上方 for(int i = x-1,j = y+1;i >= 0 && j < arr.length;i--,j++) { if(arr[i][j] == arr[x][y]) { return false; } } return true; } }
