算法——八皇后问题（eight queen puzzle）之回溯法求解

八皇后谜题是经典的一个问题，其解法一共有92种！

其定义：

首先定义一个8*8的棋盘
我们有八个皇后在手里，目的是把八个都放在棋盘中
位于皇后的水平和垂直方向的棋格不能有其他皇后
位于皇后的斜对角线上的棋格不能有其他皇后
解出能将八个皇后都放在棋盘中的摆法

这个问题通常使用两种方法来求解：

穷举法
回溯法（递归）

本文章通过回溯法来求解，回溯法对比穷举法高效许多，让我们学习如何实现吧！

实现思想：

我们先在棋盘的第0行第1个棋格放下第一个皇后
下一行寻找一个不冲突的棋格放下下一个皇后
循环第2步
如果到某一行全部8个格子都无法放下皇后，回溯到前一行，继续寻找下一个不冲突的棋格
把8个皇后都放在棋盘之后，输出或存储摆法，结束

实现（Java）算法：

定义棋盘

我们通过一个二维整型数组表示一个棋盘

数组内为1是放下了的皇后，0则是空白的棋格

我们下下面定义一个方法：通过检查棋格是否为1来知道是不是有皇后

1     // 定义一个棋盘
2     static int chessboard[][] = new int[8][8];

检查冲突

这个方法用来检查冲突：在水平垂直方向、斜角上的棋格有无其他皇后，传入的（x,y）是需要检查的棋格，如检查棋格（1,0）即棋盘的第2行第1个，是否能放下皇后。

 1     // 检查是否符合规则
 2     private static boolean checked(int x,int y){
 3         for(int i = 0;i<y;i++){
 4             // 检查水平垂直方向
 5             if(chessboard[x][i]==1)return false;
 6             // 检测左斜角
 7             if((x-y+i>=0)&&chessboard[x-y+i][i]==1)return false;
 8             // 检查右斜角
 9             if((x+y-i<=7)&&chessboard[x+y-i][i]==1)return false;
10         }
11         return true;
12     }

放下皇后

我们在每一行都执行以下步骤，通过从第1个棋格到第8个遍历寻找可以放下皇后的棋格

如果放下了皇后，我们就可以继续放下下一个了，将行数+1，我们递归调用这个方法

 1     public static boolean solve(int y){
 2         // 将一行的8种情况都扫描一次
 3         for(int i = 0;i<8;i++){
 4             // 每次检测前都将当前行清空,避免脏数据
 5             for(int k = 0;k<8;k++)chessboard[k][y]=0;
 6             if(checked(i, y)){
 7                 chessboard[i][y] = 1;
 8                 // 当前一行已经获得解法,进入下一行
 9                 solve(y+1);
10             }
11         }
12         return false;
13     }

算法边界

当我们放下了所有8个皇后后，需要一个终止条件，我们在行数y=8时，结束算法

同时你可以输出一个棋盘摆法了！恭喜你已经把这个经典问题解决了！

1         // 当y=8时,已经找到一种解决方法
2         if(y == 8){
3             return true;
4         }

以下是完整的算法

 1 public class EightQueen{
 2     // 定义一个棋盘
 3     static int chessboard[][] = new int[8][8];
 4     // 计数器
 5     static int count = 0;
 6 
 7     // 解题方法
 8     public static boolean solve(int y){
 9         // 当y=8时,已经找到一种解决方法,计数器加一并输入摆法
10         if(y == 8){
11             System.out.println("solved!");
12             show();
13             count++;
14             return true;
15         }
16         // 将一行的8种情况都扫描一次
17         for(int i = 0;i<8;i++){
18             // 每次检测前都将当前行清空,避免脏数据
19             for(int k = 0;k<8;k++)chessboard[k][y]=0;
20             if(checked(i, y)){
21                 chessboard[i][y] = 1;
22                 // 当前一行已经获得解法,进入下一行
23                 solve(y+1);
24             }
25         }
26         return false;
27     }
28     // 检查是否符合规则
29     private static boolean checked(int x,int y){
30         for(int i = 0;i<y;i++){
31             // 检查垂直方向
32             if(chessboard[x][i]==1)return false;
33             // 检测左斜角
34             if((x-y+i>=0)&&chessboard[x-y+i][i]==1)return false;
35             // 检查右斜角
36             if((x+y-i<=7)&&chessboard[x+y-i][i]==1)return false;
37         }
38         return true;
39     }
40     // 输出棋盘摆法
41     public static void show(){
42         for(int i = 0;i<8;i++){
43             for(int j = 0;j<8;j++){
44                 System.out.print(chessboard[j][i]+"  ");
45             }
46             System.out.println("");
47         }
48     }
49 }

在执行这个算法后：

have 92 ways to sovle it!

我们获得了92种棋盘摆法！