蓝桥杯基础练习 2n皇后

深碍√TFBOYSˉ_ 2022-12-03 05:17 169阅读 0赞

***目   录***

题目描述

题解

【算法】八皇后，蓝桥杯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

# 题解 #

> [原文链接][Link 1]

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;
    	}
    
    }

> ![20200901205310974.png][]

# [【算法】八皇后，蓝桥杯2n皇后 算法思路详细讲解（Java）][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;
    	}
    
    }

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][] 
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1][]

[Link 1]: https://blog.csdn.net/HC199854/article/details/104588367
[20200901205310974.png]: /images/20221123/1857fbb76ca64e6893cb8b27d1b73859.png
[2n_ _Java]: https://www.bilibili.com/video/BV1Q4411v76i
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: /images/20221123/bdbfdea6799e462baf9f7deaf880598b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1]: /images/20221123/181a8899d7dd4b34b84669e58c11ff3a.png