八皇后问题
八皇后问题
问题详述
八皇后问题：在8×8格的国际象棋上摆放八个皇后，
使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，
问有多少种摆法。
问题分析
看到这个问题首先想到的是dfs遍历得到结果，即有两个关键函数：检查是否能够放置皇后的函数check（）和遍历棋盘放置皇后的函数dfs（）。
1.首先是检查位置的函数check（），检查是否能够放置皇后，即检查是否满足如下条件：
ps：先定义两个棋盘： public static int[][] chessboard=new int[8][8];//用来存放每一种放置方法（初始全部为0，若某个格子放置一个皇后，则该位置赋值为1）
public static boolean[][] cantplace=new boolean[8][8];//用来记录每一格是否能够放置皇后（初始为false，若某个格子放置了皇后，则该位置赋值为true
另外在check（）中定义一个boolean值的变量flag用于返回boolean值
（1）横排竖排是否已经有放置的皇后：
//检查横竖是否有皇后
for(int i=0;i<8;i++) {
if(cantplace[x][i]==true||cantplace[i][y]==true) {
flag=false;
break;
}
}
（2）对角线是否已经有放置的皇后：（即y=kx+b，k=1或k=-1）
//检查对角是否有皇后,即y=kx+b
//k=1时
int m=y-x;
int n=y+x;
for(int x1=0;x1<8;x1++) {
int y1=x1+m;
if(y1<0||y1>7)
continue;
if(cantplace[x1][y1]==true) {
flag=false;
break;
}
//k=-1时
for(int x2=0;x2<8;x2++) {
int y2=n-x2;
if(y2<0||y2>7)
continue;
if(cantplace[x2][y2]==true) {
flag=false;
break;
}
}
check（）检查的条件就已经设置好了，接下来就是核心的遍历函数了。
2.遍历棋盘放置皇后的函数dfs（）即先选择第一列第一行的元素，检查第一列第一行的元素是否满足条件，满足则进入下一列，选择下一列第一行的元素，检查是否满足条件，不满足则选择该列第二行的元素，检查是否满足条件，不满足，则检查该列第三行的元素，满足则进入下一列…以此类推，若最终某一列的每一行的元素都不符合要求，则返回到上一列，选择上一列的下一行元素，当超过边界时，即已经成功的找到了一种放置方法，这时打印整个棋盘，输出一种放置方法。
（1）当x>7时即该路径放置成功，打印出该种放置方法
if(x>7) {
method++;
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++) {
System.out.print(chessboard[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
（2）遍历每一列的每一行，检查是否可以放置，可放置就进入下一列，若下一列返回到该列，说明该行放置后无解，则选择下一行，该行置为初始值
for(int i=0;i<8;i++) {
if(check(x,i)) {
cantplace[x][i]=true;
chessboard[x][i]=1;
dfs(x+1);
cantplace[x][i]=false;
chessboard[x][i]=0;
}else {
continue;
}
}
完整代码
完整代码如下：
public class Main {
public static int[][] chessboard=new int[8][8];//放置皇后的棋盘
public static boolean[][] cantplace=new boolean[8][8];//判断是否能够放置皇后
public static int method=0;//记录共有多少种方法
public static void main(String[] args) {
// TODO Auto-generated method stub
dfs(0);
System.out.println(method);
}
//检查该位置放置皇后是否符合条件,可以放置则返回true
public static boolean check(int x,int y) {
boolean flag=true;
//检查横竖是否有皇后
for(int i=0;i<8;i++) {
if(cantplace[x][i]==true||cantplace[i][y]==true) {
flag=false;
break;
}
}
//检查对角是否有皇后,即y=kx+b
//k=1时
int m=y-x;
int n=y+x;
for(int x1=0;x1<8;x1++) {
int y1=x1+m;
if(y1<0||y1>7)
continue;
if(cantplace[x1][y1]==true) {
flag=false;
break;
}
}
//k=-1时
for(int x2=0;x2<8;x2++) {
int y2=n-x2;
if(y2<0||y2>7)
continue;
if(cantplace[x2][y2]==true) {
flag=false;
break;
}
}
return flag;
}
//关键函数：遍历棋盘
public static void dfs(int x) {
//当x>7时即该路径放置成功，打印出该种放置方法
if(x>7) {
method++;
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++) {
System.out.print(chessboard[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
//遍历每一列的每一行，检查是否可以放置，可放置就进入下一列
for(int i=0;i<8;i++) {
if(check(x,i)) {
cantplace[x][i]=true;
chessboard[x][i]=1;
dfs(x+1);
cantplace[x][i]=false;
chessboard[x][i]=0;
}else {
continue;
}
}
return;
}
}
运行结果如下：
ps：共92种放置方法，在这里就不给出全部运行结果了
（希望对你有所帮助：））