今天从早上开始就在弄回溯法，都说回溯的经典问题是八皇后问题，于是就好好看了一下八皇后的问题。找出所有的情况可能有点难，但是找出一条路来感觉应该挺简单的。

     我一直都不怎么会用递归，这个程序依然没有递归。

1.  
2. /*这个算法主要解决八皇后问题*/ 
3.  
4. public class Huisu02 {  
5.     //判断当前点是否处于以前点的对角线上  
6.     public static boolean isdianogal(int x,int y,int[] points){
   //把当前点的位置传过去 这里y有两个作用：表示当前点的坐标，表示points中点的个数  
7.         //判断正对角线   \  
8.         int xx=0,yy=0;  
9.         xx=x>y?x-y: 0;  
10.         yy=x>y? 0 :y-x;  
11.         for (int i = yy; i < y; i++) {
    //这里必须从yy开始 因为需要判断x<y的情况  
12.             if(points[i]==xx){  
13.                 return true;  
14.             }  
15.             xx++;yy++;  
16.         }  
17.         //判断反对角线    /  
18.         xx=x+y<=7?x+y:7;  
19.         yy=x+y<=7?0:x+y-7;  
20.         for (int i = yy; i < y; i++) {
    //这里必须从yy开始 因为需要判断x<y的情况  
21.             if(points[i]==xx){  
22.                 return true;  
23.             }  
24.             xx--;yy++;  
25.         }  
26.         return false;  
27.     }  
28.     public static void huisu(){  
29.           
30.     }  
31.     public static void main(String[] args) {  
32.       
33.         int[] samerow = new int[8];// 判断是否同列  
34.         int[] points=new int[8];//存储点的x轴的坐标  
35.         int index=0;  
36.         boolean backed=false;  
37.         points[index++]=0;  
38.         samerow[0]=1;  
39.         while (index<8) {  
40.             int i=0;  
41.             if(!backed){  
42.                 for (i = 0; i < points.length; i++) {  
43.                     if(samerow[i]==0){
    //这一列是可选的  
44.                         if(!isdianogal(i, index, points)){
    //不在对角线内  
45.                             points[index++]=i;  
46.                             samerow[i]=1;  
47.                             break;  
48.                         }  
49.                     }  
50.                 }  
51.             }else {  
52.                 for (i = points[index]+1; i < points.length; i++) {  
53.                     if(samerow[i]==0){
    //这一列是可选的  
54.                         if(!isdianogal(i, index, points)){
    //不在对角线内  
55.                             points[index++]=i;  
56.                             backed=false;  
57.                             samerow[i]=1;  
58.                             break;  
59.                         }  
60.                     }  
61.                 }  
62.             }  
63.               
64.             if(i>=8){
    //这一行已经没有可以选择的了  退回到上一行去  
65.                   
66.                 index--;  
67.                 samerow[points[index]]=0;  
68.                 backed=true;  
69.             }  
70.         }  
71.         //把得到的结果反映到棋盘上面去  
72.         int[][] cheesbord = new int[8][8];// 代表棋盘放置了皇后就为1，没放就是0  
73.         int j=0;  
74.         for (int i = 0; i < points.length; i++) {  
75.             cheesbord[i][points[j]]=1;  
76.             j++;  
77.         }  
78.           
79.         for (int i = 0; i < 8; i++) {  
80.             for (j = 0; j < 8; j++) {  
81.                 if(cheesbord[i][j]==1){  
82.                     System.err.print(cheesbord[i][j]+" ");  
83.                 }  
84.                 System.err.print("# ");  
85.             }  
86.             System.err.println();  
87.         }  
88.     }  
89. }  

对于八皇后问题的描述在ppt里面。