当前位置:   article > 正文

【DFS经典例题】2n皇后问题

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 1
1 1 1 1
样例输出
2


先来解读一下题意:我们需要在一个n<8的n*n的棋盘上放两个颜色的皇后,同一行或列、同一斜线上不能有同一种颜色的皇后。跟经典的八皇后问题类似,我们可以用递归或者回溯。
题目中的实例讲的很明白,我就不多重复了。我们做这样的算法题,主要目的就是让程序按照相应的步骤来执行,所以说我们只需要按照他给定的思路一步步的写下去即可。
首先,我们需要定义两个全局变量,一个是用来存储棋盘的二维数组,一个是记录有多少种方法的answer
我们假设黑皇后用2表示,白的用3表示,下面就是遍历棋盘,符合条件的标注为相应的数字。

  • 这里有这样几个难点:首先,我们需要怎样遍历才能完美的判断出皇后的位置?其次,判断是否符合条件时我们的思路以及相应的程序是怎样的?
  1. 第一个问题:

我上面提到了,我们在这里用到的是回溯和递归,我们定义的这个方法需要传两个参数,第一个是n,也就是从第n行开始,第二个是d,也就是皇后的颜色,在这里d只能取2和3。
我们初次调用此方法是先放黑皇后,d一开始等于2,进来之后是个for循环,先假设第一个没有棋子的地方符合,标记之后判断是否符合,如果符合,进入下一行,如果不符合,取消标记,并继续循环查看本行的下一个位置。

  • 注意,如果符合,我们要递归调用本方法而不是继续循环;如果不符合我们需要取消标记并继续循环,不要混了。不符合的情况用到了回溯,符合以及后面的一个情况用到了递归。

检查完黑皇后之后,我们让d变成3继续上面的操作,符合相应的条件后便退出程序显示结果,我相信大家应该可以看明白这些地方。

  1. 第二个问题:

判断是否符合条件,这里需要特别注意设定的边界值,防止数组角标越界。

  • 我们需要特别判断同一列,左斜上方,右斜上方。斜下方就不需要了,因为我们放棋子是从上往下放的,下面是不可能有的。

每一次判断的依据就是这一行或列是否有与这个位置相同的数字。用三个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;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/825443
推荐阅读
相关标签
  

闽ICP备14008679号