欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯 DFS 2n皇后问题(困难)

程序员文章站 2022-05-21 15:18:46
...

 

问题描述

  给定一个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

解题思路

皇后摆放的限制:使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。

1.只有不断遍历棋盘的位置,不断验证此位置是否通过皇后的摆放限制

2.通过皇后摆放限制,放下棋子,挂起方法,继续遍历下一个位置摆放皇后

3.摆放到最后,开始从头开始遍历白皇后(一开始摆放的是黑皇后)

4.黑白摆放完毕(这只是一种摆法),回溯到最开始摆放的位置,还原未摆放此位置的状态,继续向下一位置摆放(递归回溯)

参考代码

public class Main {
	 
	// 皇后/棋盘的个数
	private static final int QUEEN_NUM = 4;
 
	// 首先定义一个8 * 8 的棋盘
	private static final int[][] Checkerboard = new int[QUEEN_NUM][QUEEN_NUM];
 
	// 定义一共有多少种放置皇后的算法
	private static int COUNT = 0;
	
	private static int color = 2;
 
	/**
	 * 打印棋盘
	 */
	public static final void show() {
		System.out.println("第" + (++COUNT) + "次摆法");
		for (int i = 0; i < QUEEN_NUM; i++) {
			for (int j = 0; j < QUEEN_NUM; j++) {
				System.out.print(Checkerboard[i][j] + " ");
			}
			System.out.println("");
		}
	}
 
	public static final boolean check(int row, int col) {
 
		// 判断当前位置的上面是否有皇后
		for (int i = row - 1; i >= 0; i--) {
			if (Checkerboard[i][col] == color)
				return false;
		}
 
		// 判断左上是否有皇后
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
			if (Checkerboard[i][j] == color)
				return false;
		}
 
		// 判断右上是否有皇后
		for (int i = row - 1, j = col + 1; i >= 0 && j < QUEEN_NUM; i--, j++) {
			if (Checkerboard[i][j] == color)
				return false;
		}
 
		return true;
	}
 
	/**
	 * 从第n行放置皇后
	 * 
	 * @param row
	 */
	public static final void play(int row) {
		// 遍历当前行的所有单元格 以列为单元
		for (int i = 0; i < QUEEN_NUM; i++) {
			if (Checkerboard[row][i] != 0) {
				continue;
			}
			// 是否能够放置皇后
			if (check(row, i)) {
				Checkerboard[row][i] = color;
 
				if (row == QUEEN_NUM - 1) {
					// 最后行 放置完毕 打印皇后
					if (color == 2) {
						color++;//摆放2结束,摆放3
						play(0);//重头开始
					}
					if(color == 3){
						show();//摆法结束
						color = 2;//颜色归为2
					}
				} else {
					// 放置下一行
					play(row + 1);
				}
 
				//回退到当前步骤,把皇后设置为0
				Checkerboard[row][i] = 0;
			}
 
		}
	}
 
	public static void main(String[] args) {
		play(0);
	}
}