1 package 回溯; 2  3 public class 八皇后递归回溯 { 4  5     private int length;                  //皇后数量 6     private int sum;                     //总方案数 7     private int num[];                   //存放皇后的一维数组 8  9     public 八皇后递归回溯() {10         length = 8;11         sum=0;12         num = new int[length + 1];13     }14     15     public boolean check(int x) {16         for (int i = 1; i < x; ++i) {    //在一列，或对角线17             if (num[x] == num[i]|| Math.abs(x - i) == Math.abs(num[x] - num[i]))18                 return false;19         }20         return true;21     }22 23     public void reback(int x) {24         if (x > length) {25             for (int i = 1; i <= length; ++i) {26                 System.out.print(num[i] + " ");27             }28             System.out.println();29             sum++;30         } else {31             for (int i = 1; i <= length; ++i) {32                 num[x] = i;33                 if (check(x)) reback(x + 1);    //第x个皇后找到位置，则继续第x+1个,i=1的方案完毕后继续i=2的方案34             }35         }36     }37 38     public static void main(String[] args) {39         八皇后递归回溯 test=new 八皇后递归回溯();40         test.reback(1);41         System.out.println("共"+test.sum+"种方案");42     }43 }

回溯算法的原则：不进则退。讲搜索空间看成树，可采用深度优先、广度优先等策略进行搜索，上述所示八皇后采用深度优先策略