蓝桥杯 基础练习 2n皇后

目   录

题目描述

题解

【算法】八皇后，蓝桥杯2n皇后 算法思路详细讲解（Java）

---

题目描述

题目描述
给定一个 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

题解

原文链接

package B基础练习;

import java.util.*;

public class A27_2n皇后2 {

	static int n;
	static int count = 0; // 统计
	static boolean flag = true; // 用于标记是在放白棋子还是黑棋子

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		int[][] arr = new int[n][n];
		int[] white = new int[n];
		int[] black = new int[n];
		for (int i = 0; i < n; i++) {
			white[i] = Integer.MAX_VALUE;
			black[i] = Integer.MAX_VALUE;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = scanner.nextInt();
			}
		}
		dfs(arr, white, black, 0);
		System.out.println(count);
	}

	private static void dfs(int[][] arr, int[] white, int[] black, int row) {
		if (row == white.length) {
			if (flag) {
				flag = !flag;
				// 用交换参数位置，进行黑色棋子的摆放
				dfs(arr, black, white, 0);// 白色棋子放完后，开始放黑色棋子
				flag = !flag;// 回溯
			} else {// 两种棋子都放完了
				count++;
			}
			return;
		}
		for (int i = 0; i < n; i++) {
			if (check(arr, white, row, i)) {
				white[row] = i;
				if (flag)
					arr[row][i] = 2;
				else
					arr[row][i] = 3;
				dfs(arr, white, black, row + 1);
				white[row] = Integer.MAX_VALUE;
				arr[row][i] = 1;// 回溯
			}
		}
	}

	private static boolean check(int[][] arr, int[] a, int x, int y) {
		if (arr[x][y] == 2)
			return false;// 白色棋子占了
		if (arr[x][y] == 0)
			return false;// 这个位置不能放皇后
		for (int i = 0; i < a.length; i++) {
			if (a[i] == y)// 检查列
				return false;
			if (i - a[i] == x - y)// 检查主对角线
				return false;
			if (i + a[i] == x + y)// 检查副对角线
				return false;
		}
		return true;
	}

}

【算法】八皇后，蓝桥杯2n皇后 算法思路详细讲解（Java）

package B基础练习;

public class A27_2n皇后 {

	static int n = 4, count; // n阶棋盘

	public static void main(String[] args) {
		int[][] mainChess = new int[n][n];
//		for (int i = 0; i < n; i++) { // Java数组初始化元素默认为0
//			for (int j = 0; j < n; j++) {
//				mainChess[i][j] = 0;
//			}
//		}
		putChess(0, mainChess);
	}

	public static void putChess(int row, int[][] chess) {
		int[][] currentChess = (int[][]) chess.clone();
		if (row == n) {
			count++;
			System.out.println("第" + count + "种：");
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					System.out.print(currentChess[i][j]);
				}
				System.out.println();
			}
			System.out.println();
			return;
		} else {
			for (int i = 0; i < n; i++) {
				if (!isDanger(row, i, currentChess)) {
					for (int j = 0; j < n; j++) {
						currentChess[row][j] = 0;
					}
					currentChess[row][i] = 1;
					putChess(row + 1, currentChess);
				}
			}
		}
	}

	public static boolean isDanger(int row, int col, int[][] currentChess) {
		for (int i = 0; i < row; i++) {
			if (currentChess[i][col] == 1) {
				return true;
			}
			for (int j = 0; j < n; j++) {
				if (((row + col) == (i + j) || (row - col) == (i - j)) && currentChess[i][j] == 1) {
					return true;
				}
			}
		}
		return false;
	}

}