本文共 2280 字，大约阅读时间需要 7 分钟。
2n皇后 问题描述给定一个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 11 1 1 1
样例输出： 2 样例输入： 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出：0
思路：基本思路和8皇后相同，不同之处在于情况不仅是位置不同决定的，同一个位置不同颜色的棋子还有不同的结果。为了分区分，用2代表白皇后占的位置，用3代表黑皇后占的位置。我们规定先放白皇后，首先检查是否为1，如果不为1则该位置不可放置，continue检查下一个位置。如果可放，检查是否符合约束函数check()；如果不符合，continue检查下一个位置。如果符合，本行放置结束，执行putQueen(m+1, queen)递归下一行。同时注意回溯。
import java.util.Scanner; public class Main { static int n; static int[][] chess; static int count = 0; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); chess = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { chess[i][j] = in.nextInt(); } } // 白皇后记为2，黑皇后记为3，先放白皇后 putQueen(0, 2); System.out.println(count); } public static void putQueen(int m, int queen) { if (m > n - 1) { if (queen == 2) { putQueen(0, 3); } else { count++; } return; } for (int i = 0; i < n; i++) { // 如果位置为0或者queen已放置，则不能放置 if (chess[m][i] ！= 1) { continue; } // 如果可放，则记录;反之，检查下一列 if (check(m, i, queen)) { chess[m][i] = queen; } else { continue; } // 继续判断下一行 putQueen(m + 1, queen); // 回溯，这里不用考虑0的位置，因为在上面已经被筛掉了，非常巧妙 chess[m][i] = 1; } } public static boolean check(int row, int col, int queen) { int step = 1; while(row - step >= 0){ if(chess[row-step][col] == queen) { //上 return false; } if(col-step >= 0 && chess[row-step][col-step] == queen) { //左上 return false; } if(col+step < n && chess[row-step][col+step] == queen) { //右上 return false; } step++; } return true; }} 转载地址：http://erjaf.baihongyu.com/