八皇后谜题是经典的一个问题，其解法一共有种！
其定义：
- 首先定义一个8*8的棋盘
- 我们有八个皇后在手里，目的是把八个都放在棋盘中
- 位于皇后的水平和垂直方向的棋格不能有其他皇后
- 位于皇后的斜对角线上的棋格不能有其他皇后
- 解出能将八个皇后都放在棋盘中的摆法
这个问题通常使用两种方法来求解：
- 穷举法
- 回溯法（递归）
本文章通过回溯法来求解，回溯法对比穷举法高效许多，让我们学习如何实现吧！
实现思想：
- 我们先在棋盘的第0行第1个棋格放下第一个皇后
- 下一行寻找一个不冲突的棋格放下下一个皇后
- 循环第2步
- 如果到某一行全部8个格子都无法放下皇后，回溯到前一行，继续寻找下一个不冲突的棋格
- 把8个皇后都放在棋盘之后，输出或存储摆法，结束
实现（Java）算法：
定义棋盘
我们通过一个二维整型数组表示一个棋盘
数组内为1是放下了的皇后，0则是空白的棋格
我们下下面定义一个方法：通过检查棋格是否为1来知道是不是有皇后
// 定义一个棋盘
static int chessboard[][] = new int[8][8];
检查冲突
这个方法用来检查冲突：在水平垂直方向、斜角上的棋格有无其他皇后，传入的（x,y）是需要检查的棋格，如检查棋格（1,0）即棋盘的第2行第1个，是否能放下皇后。
// 检查是否符合规则
private static boolean checked(int x,int y){
for(int i = 0;i<y;i++){
// 检查水平垂直方向
if(chessboard[x][i]==1)return false;
// 检测左斜角
if((x-y+i>=0)&&chessboard[x-y+i][i]==1)return false;
// 检查右斜角
if((x+y-i<=7)&&chessboard[x+y-i][i]==1)return false;
}
return true;
}
放下皇后
我们在每一行都执行以下步骤，通过从第1个棋格到第8个遍历寻找可以放下皇后的棋格
如果放下了皇后，我们就可以继续放下下一个了，将行数+1，我们递归调用这个方法
public static boolean solve(int y){
// 将一行的8种情况都扫描一次
for(int i = 0;i<8;i++){
// 每次检测前都将当前行清空,避免脏数据
for(int k = 0;k<8;k++)chessboard[k][y]=0;
if(checked(i, y)){
chessboard[i][y] = 1;
// 当前一行已经获得解法,进入下一行
solve(y+1);
}
}
return false;
}
算法边界
当我们放下了所有8个皇后后，需要一个终止条件，我们在行数y=8时，结束算法
同时你可以输出一个棋盘摆法了！恭喜你已经把这个经典问题解决了！
// 当y=8时,已经找到一种解决方法
if(y == 8){
return true;
}
以下是完整的算法
public class EightQueen{
// 定义一个棋盘
static int chessboard[][] = new int[8][8];
// 计数器
static int count = 0;
// 解题方法
public static boolean solve(int y){
// 当y=8时,已经找到一种解决方法,计数器加一并输入摆法
if(y == 8){
System.out.println("solved!");
show();
count++;
return true;
}
// 将一行的8种情况都扫描一次
for(int i = 0;i<8;i++){
// 每次检测前都将当前行清空,避免脏数据
for(int k = 0;k<8;k++)chessboard[k][y]=0;
if(checked(i, y)){
chessboard[i][y] = 1;
// 当前一行已经获得解法,进入下一行
solve(y+1);
}
}
return false;
}
// 检查是否符合规则
private static boolean checked(int x,int y){
for(int i = 0;i<y;i++){
// 检查垂直方向
if(chessboard[x][i]==1)return false;
// 检测左斜角
if((x-y+i>=0)&&chessboard[x-y+i][i]==1)return false;
// 检查右斜角
if((x+y-i<=7)&&chessboard[x+y-i][i]==1)return false;
}
return true;
}
// 输出棋盘摆法
public static void show(){
for(int i = 0;i<8;i++){
for(int j = 0;j<8;j++){
System.out.print(chessboard[j][i]+" ");
}
System.out.println("");
}
}
}
在执行这个算法后：
have 92 ways to sovle it!
我们获得了92种棋盘摆法！