八皇后问题简易解答（回溯法）

由于我水平有限，本文参考了网上的各个做法，选取了我最能理解的解法，我尽量地解释这个解法来检验我对本问题的理解程度（只写出最终的解法数量）。

八皇后问题讲的是8个皇后棋在一个8*8的棋盘上，谁都不能攻击到对方，皇后的攻击方向有横竖斜三个方向，不同的摆放形成不同的解法。

其实就是一个给皇后找位置的游戏，先确定第一个皇后的位置，剩下的逐行根据规则确定，成功的输出，失败的返回上一个位置试下一个位置，直到8个皇后全部选好位置。

以下是具体的代码(java)

 1 //8皇后问题 2 public class Queen 3 {   4   private int[] column; //同列是否有皇后，1表示有,0表示没有 5   private int[] rsl;  //右上至左下是否有皇后 6   private int[] lsl;  //左上至右下是否有皇后 7   private int[] queen; //皇后编号 8   private static int num;//答案数量 9   public Queen()10   {11     column=new int[9];12     rsl=new int[17];13     lsl=new int[17];14     for(int i=1;i<=8;i++)     15     {16      column[i]=0;         //初始定义全部无皇后17     }18     for(int i=1;i<=16;i++)19     {20      rsl[i]=lsl[i]=0; 21     }22     queen=new int[9];23   }24   public void backtrack(int i)  //这里的i才是行数25   {26     if(i>8)27     {28         num++;  //最后大于8表示8个皇后都找到了位置，解答数加一29     }30     else31     {32       for(int j=1;j<=8;j++)33        {34          if((column[j]==0)&&(rsl[i+j]==0)&&(lsl[i-j+8]==0))//判断横竖斜有没有皇后35          {36             queen[i]=j;//皇后位置37             column[j]=rsl[i+j]=lsl[i-j+8]=1;//设定为占用38             backtrack(i+1); //循环调用39             column[j]=rsl[i+j]=lsl[i-j+8]=0;//再定义无皇后 40          }41        }42     }43   }44   public static void main(String[]args)45   {46     Queen queen=new Queen();47     queen.backtrack(1);//开始回溯法，从行1开始48     System.out.println("\n解答数为"+num); //输出总解答数  49   }50 }

所谓回溯就是不停的尝试，遇到错误答案时，直接放弃错误条件，回到上一步改变条件继续。上面的代码中，在确定了第一行第一个皇后位置后，将能攻击的位置都标示出来，再调用函数尝试第二行也就是第二个皇后的位置，满足条件就继续第三个，不满足就调用结束，初始化条件，同理直到8位皇后都确定。这种取消了错误条件继续运行步骤的方法，大大减少了运行时间。

相同方法的还有迷宫问题。

原标题：八皇后问题简易解答（回溯法）

关键词：