蓝桥杯基础练习VIP-2n皇后问题-题解（Java代码）

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class llq1{

static int n,ans;

static int[][]a=new int[10][10];

static int vis_white_lie[]=new int[10];

static int vis_white_left[]=new int[20];

static int vis_white_right[]=new int[20];

static int white[][]=new int[10][10];

static int vis_black_lie[]=new int[10];

static int vis_black_left[]=new int[20];

static int vis_black_right[]=new int[20];

public static void main(String[] args) {

Scanner s=new Scanner(System.in);

n=s.nextInt();

for(int i=1;i<=n;i++) {

for(int j=1;j<=n;j++) {

a[i][j]=s.nextInt();

}

}

dfs_white(1);

System.out.println(ans);

}

private static void dfs_white(int x) {

//先考虑白皇后，再考虑黑皇后，每完成一种情况就dfs_black递归找黑皇后的情况

if(x==n+1)//白皇后已经完成了n行，准备进入第n+1行就是白皇后已经放完了

{

dfs_black(1);//递归调用黑皇后

return;

}

for(int i=1;i<=n;i++) {

if(vis_white_lie[i]==0&&vis_white_left[x+i]==0&&vis_white_right[x-i+n]==0&&a[x][i]!=0) {

//如果列，左斜线，右斜线都没有被占用，并且格子不为0

{

vis_white_lie[i]=1;

vis_white_left[x+i]=1;//左斜线x,y相加相等

vis_white_right[x-i+n]=1;//右斜线x,y坐标相减相等

white[x][i]=1;//将白皇后占的格子标记上，用于禁止黑皇后使用

dfs_white(x+1);//尝试第x+1行

vis_white_lie[i]=0;

vis_white_left[x+i]=0;

vis_white_right[x-i+n]=0;

white[x][i]=0;

}

}

}

}

private static void dfs_black(int x) {

// TODO Auto-generated method stub

if(x==n+1)

{

ans++;

return;

}

for(int i=1;i<=n;i++) {

if(vis_black_lie[i]==0&&vis_black_left[x+i]==0&&vis_black_right[x-i+n]==0&&a[x][i]!=0&&white[x][i]==0) {

//如果列，左斜线，右斜线都没有被占用，并且格子不为0,不被白皇后占用

{

vis_black_lie[i]=1;

vis_black_left[x+i]=1;//左斜线x,y相加相等

vis_black_right[x-i+n]=1;//右斜线x,y坐标相减相等

dfs_black(x+1);//尝试第x+1行

vis_black_lie[i]=0;//回溯

vis_black_left[x+i]=0;

vis_black_right[x-i+n]=0;

}

}

}

}

}