蓝桥杯 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);
}
}