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

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

其定义：

首先定义一个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种棋盘摆法！

巴特西