腾科java培训的八皇后的问题

把棋盘看成二维方阵，行从上到下编号0-7（就是i），列从左到右编号0-7（就是j），这样棋盘上每个点都可以表示为（i，j）
从键盘的右上角（0，7）到左下角（7，0）的对角线，以及这条线的平行线，就是反对角线，也就是这个程序里的undiagonal。显然这个反对角线上任意2点（i1，j1）和（i2，j2）都满足i1+j1=i2+j2.因为i+j可能的取值范围是从0到14，所以把这个数组的长度定义为16（事实上15就可以了）
从键盘的左上角（0，0）到右下角（7，7）的对角线以及平行线，就是对角线，就是diagonal。同理，这个对角线及其平行线上任意2点都满足i1-i2=j1-j2.i-j的范围是-7到7，为了避免出现负数，程序里在这里+7，也是一个长度为16的数组（还是15就够了）
程序一开始的时候，i=j=0，所有的安全标识都是true，所以（0，0）这个点会被输出。这时，把diagonal【7】置为false。因为（1，1），（2，2）等等这些点都和（0，0）在一条对角线上（因为0-0+7=1-1+7=2-2+7），所以把这些点的对应的diagonal都置为false，也就是把diagonal【7】置为false
并且把undiagonal【0】也置为false，但是因为undiagonal【0】对应的元素只有（0，0）（因为只有0+0=0），所以这个对这一步没什么影响。
然后一点点递推，回溯，步骤就是这样.
public class Queen {
 int num; // 记录方案数
 int[] queenline = new int[8]; // 记录8个皇后所占用的列号
 boolean[] col = new boolean[8]; // 列安全标志
 boolean[] diagonal = new boolean[16]; // 对角线安全标志
 boolean[] undiagonal = new boolean[16]; // 反对角线安全标志
 void solve(int i) {
  for (int j = 0; j < 8; j++) {
   if (col[j] && diagonal[i - j + 7] && undiagonal[i + j]) {
    // 表示第i行第j列是安全的可以放皇后
    queenline[i - 1] = j + 1;
    col[j] = false; // 修改安全标志
    diagonal[i - j + 7] = false;
    undiagonal[i + j] = false;
    if (i < 8) // 判断是否放完8个皇后
    {
     solve(i + 1); // 未放完8个皇后则继续放下一个
    } else // 已经放完8个皇后
    {
     num++;
     System.out.println("\n皇后摆放第" + num + "种方案:");
     System.out.println("行分别为1 2 3 4 5 6 7 8 ");
     System.out.print("列分别为");
     for (int i1 = 0; i1 < 8; i1++)
      System.out.print(queenline[i1] + " ");
    }
    col[j] = true; // 修改安全标志，回溯
    diagonal[i - j + 7] = true;
    undiagonal[i + j] = true;
   }
  }
 }
 public static void main(String[] args) {
  Queen q = new Queen();
  System.out.println("////八皇后问题////");
  q.num = 0; // 方案初始化
  for (int i = 0; i < 8; i++)
   // 置所有列为安全
   q.col[i] = true;
  for (int i0 = 0; i0 < 16; i0++)
   // 置所有对角线为安全
   q.diagonal[i0] = q.undiagonal[i0] = true;
  q.solve(1);
 }
}
详情请登陆： www.togogo.net 、http://weibo.com/togogoit
欢迎拨打咨询热线： 020-38289118、4008852225
联系地址：广州市天河区科韵北路188号乐天大厦2楼(腾科IT教育)