WUSTOJ 1291: 2n皇后问题（Java）

题目：?1291: 2n皇后问题

前言?

上次写了?N皇后问题，这是第二次写回溯了，总算有种熟悉的感觉了。我还听说昨天软件设计师考了皇后问题。经典果然重要。。?

Description

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

Input

多组测试数据，每组数据的输入格式如下。 第一行为一个整数n，表示棋盘的大小。 接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

Output

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

Sample Input

4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output

2 0

分析?

这道题目，相对于N皇后问题，增加了两点：

设置棋盘为0的位置无法放置皇后有黑皇后和白皇后两种

但是都思路相差不大。每个皇后用三个数组分别保存N列的情况，2*N-1条正斜线，2*N-1条反斜线的皇后情况，判断是否能放皇后即可。区别是这里用到两层循环，分别放黑皇后和白皇后。当然回溯结束还要恢复到初始情况进行下一行的回溯。

代码?

/** * Time 566ms * @author wowpH * @version 2.3 * @date 2019年5月26日下午8:39:37 * Environment: Windows 10 * IDE Version: Eclipse 2019-3 * JDK Version: JDK1.8.0_112 */ import java.util.Scanner; public class Main { private static final int MAX_N = 8; private Scanner sc; private int n; // 棋盘大小 private int[][] board; // 棋盘情况，1可以放皇后，0不能放皇后 // 每列的皇后情况，true有，false没有，下标从0开始 private boolean[] columnBlack; private boolean[] columnWhite; // 正斜线的皇后情况，true有，false没有，下标从0开始 private boolean[] slashBlack; private boolean[] slashWhite; // 反斜线的皇后情况，true有，false没有，下标从1开始 private boolean[] backSlashBlack; private boolean[] backSlashWhite; private int solution; // 放法的数量 public Main() { init(); // 初始化 sc = new Scanner(System.in); while (sc.hasNext()) { input(); // 输入棋盘情况 solution = 0; // 初始0种放法 backTrack(0); // 回溯，第0行开始 System.out.println(solution); } sc.close(); } private void init() { board = new int[MAX_N][MAX_N]; // 棋盘 columnBlack = new boolean[MAX_N]; // 列 columnWhite = new boolean[MAX_N]; slashBlack = new boolean[2 * MAX_N - 1];// 斜线 slashWhite = new boolean[2 * MAX_N - 1]; backSlashBlack = new boolean[2 * MAX_N];// 反斜线 backSlashWhite = new boolean[2 * MAX_N]; } private void input() { n = sc.nextInt(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j] = sc.nextInt(); } } } private void backTrack(int row) { if (row >= n) { // 回溯结束条件 solution++; return; } for (int i = 0; i < n; i++) { // 在第i列上放黑皇后 if (0 == board[row][i]) { // row行i列是否能放皇后 continue; // 0，不能放 } if (columnBlack[i]) { // i列上是否有黑皇后 continue; // 有，不能放 } // 正反斜线上是否有皇后 if (slashBlack[row + i] || backSlashBlack[n - row + i]) { continue; // 有，不能放 } // 可以放黑皇后 columnBlack[i] = true; slashBlack[row + i] = true; backSlashBlack[n - row + i] = true; for (int j = 0; j < n; j++) { // j列上放白皇后 if (j == i || 0 == board[row][j]) {// 有黑皇后或者不能放皇后 continue; } if (columnWhite[j]) { // 第j列是否有白皇后 continue; // 有，不能放 } // 正反斜线是否有白皇后 if (slashWhite[row + j] || backSlashWhite[n - row + j]) { continue; // 有不能放 } // 可以放白皇后 columnWhite[j] = true; slashWhite[row + j] = true; backSlashWhite[n - row + j] = true; // 回溯下一行 backTrack(row + 1); // 下层回溯结束，恢复白皇后情况 columnWhite[j] = false; slashWhite[row + j] = false; backSlashWhite[n - row + j] = false; } // 下层回溯结束，恢复黑皇后情况 columnBlack[i] = false; slashBlack[row + i] = false; backSlashBlack[n - row + i] = false; } } public static void main(String[] args) { new Main(); } }

---

版权声明：

转载请于首页注明链接形式的WUSTOJ 1291: 2n皇后问题（Java）——wowpH；代码原创，公开引用不能删除首行注释（作者，版本号，时间等信息）；如果有疑问欢迎评论区留言，尽量解答；如果有错误，还望大侠评论区指正。

---