本文主要是介绍蓝桥杯vip试题 基础练习 2n皇后问题（java实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
给定一个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
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
我的分析：这里的2n皇后（黑白两个）和n皇后问题确实没太大区别，这里就从n皇后问题开始分析。这里它要求棋盘是随机地摆放0和1，所以还是得用个二维数组来表示棋盘，数组元素就存储0或1，黑或白。这个问题按经典算法分为两个部分，如何查找和如何判断。如何查找就是怎样遍历完整个棋盘，找到确定位置；如何判断就是怎样判断当前位置是“正确”的。
我们可以从第一个位置开始检索，从左到右，从上到下。因为要求不能在同一行，所以在当前行找到位置后就可以直接跳转到下一行 查找下一行的位置。因为每一行都是从第一个开始检索并且找到后就立即跳到下一行，所以不用判断同一行是否有相同皇后。我们只需要判断图中的三条红线，即列、左对角线和右对角线。又因为从左到右、从上到下的检索顺序，所以我们只用判断“前半部分”，后面的都还没有检索，所以肯定没有相同元素。如何判断就这样啦，接下来仔细思考如何查找。
用回溯的话，它是检索到了位置不对的地方，就马上回到上一行更变位置。比如我现在找到了第3行，但是每一列的位置都与上面摆好的位置冲突，我们这时就要回退到第2行，假设第2行第4列是之前摆好的，所以我们就是回退到（2，4），然后移到下一个位置也就是（2，5），不能往前移，因为前面的位置都是与上面的位置不符的，所以只能往后移，后面的都是没有检索过的位置。每次回退后，（2，4）这个原位置就要变回1，因为它已经不被我们所用，要及时变回原样。还有就是，当黑白皇后都摆好后，这时count++，函数也要回退，回退摆好的位置就会变为1，因为我们还要找新的摆放位置，所以这是必要的。我最开始还有个疑惑，黑的先还是白的先，黑白位置互换又是一种新的摆法，岂不是最后结果还要乘2？但是回溯的精妙之处解决了这些问题。回退是从后往前回退，第5行的所有可能找完后，它会回退到第4行，又换新的位置摆放，就这样它会回退到最初的第一行第一列这个位置，然后移到（1，2）这个又找新的摆放位置，这样的话，假设我们白的先，（1，1）刚才是被白的占了，现在白的移到（1，2），那么黑的就有机会移到（1，1）这个位置，所以我之前的顾虑黑白位置互换又乘2，是完全不用的。回溯法真的很暴力，它遍历了所有的可能性，以至于保证了我们结果的准确性。这里我们规定2表示白皇后，3表示黑皇后。
import java.util.Scanner;public class Main {//用来存放棋盘static int[][] chessboard;//棋盘的“阶数”static int n;//皇后摆放的种类次数static int count;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();chessboard = new int[n][n];for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) chessboard[i][j] = in.nextInt();//默认从第0行开始，先找白皇后dfs(0, 2);System.out.println(count);in.close();}/*** 判断当前位置是否能放* @param x 行坐标* @param y 列坐标* @param type 是白是黑* @return*/public static boolean check(int x, int y, int type) {if (chessboard[x][y] != 1) return false;//判断当前列上是否有相同皇后for (int i = 0; i < x; i++) if (chessboard[i][y] == type) return false;//判断右对角线上是否有相同元素for (int i = x - 1, j = y + 1; i > -1 && j < n; i--, j++) if (chessboard[i][j] == type) return false;//判断左对角线上是否有相同元素for (int i = x - 1, j = y - 1; i > -1 && j > -1; i--, j--) if (chessboard[i][j] == type) return false;return true;}/*** 摆放位置可以看作是找一条“通路”，当前位置不行就回退用dfs（回溯法）* @param row 棋盘的行数* @param type 2表示白皇后，3表示黑皇后*/public static void dfs(int row, int type) {//最后一行判断if (row == n) {if (type == 2) //如果白皇后确定好位置就开始摆黑皇后位置dfs(0, 3);else//若黑皇后摆好次数就加1count++;return;}//i表示列数，行数通过递归增长for (int i = 0; i < n; i++) if (check(row, i, type)) {chessboard[row][i] = type;//这一行找好后就直接去下一行找dfs(row + 1, type);//找完回退到这里，这个位置就变成原样，为了找新的摆放位置chessboard[row][i] = 1;}}}这篇关于蓝桥杯vip试题 基础练习 2n皇后问题（java实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
