帮解读1下八皇后的程序，谢谢

Question

package javabase;/**
 * <p>Title: </p>
 *
 * <p>Description: JAVA基础算法</p>
 *
 * <p>Copyright: Copyright (c) 2009</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
public class Queen {
    // 同栏是否有皇后，1表示有
    private int[] column;
    // 右上至左下是否有皇后
    private int[] rup;
    // 左上至右下是否有皇后
    private int[] lup;
    // 解答
    private int[] queen;
    // 解答编号
    private int num;    public Queen() {
        column = new int[8 + 1];
        rup = new int[2 * 8 + 1];
        lup = new int[2 * 8 + 1];
        for (int i = 1; i <= 8; i++) {
            column[i] = 1;
        }
        for (int i = 1; i <= 2 * 8; i++) {
            rup[i] = lup[i] = 1;
        }
        queen = new int[8 + 1];
    }    public void backtrack(int i) {
        if (i > 8) {
            showAnswer();
        } else {
            for (int j = 1; j <= 8; j++) {
                if (column[j] == 1 && rup[i + j] == 1 && lup[i - j + 8] == 1) {
                    queen[i] = j; // 设定为占用
                    column[j] = rup[i + j] = lup[i - j + 8] = 0;
                    backtrack(i + 1);
                    column[j] = rup[i + j] = lup[i - j + 8] = 1;
                }
            }
        }
    }    protected void showAnswer() {
        num++;
        System.out.println("\n解答 " + num);
        for (int y = 1; y <= 8; y++) {
            for (int x = 1; x <= 8; x++) {
                if (queen[y] == x) {
                    System.out.print("  Q");
                } else {
                    System.out.print("  .");
                }
            }
            System.out.println();
        }
    }    public static void main(String[] args) {
        Queen queen = new Queen();
        queen.backtrack(1);
    }
}

Answer 1

今天打开csdn看到的第一个帖子就是你的这个帖子，但是一直没时间细看下去。我之前在blog中写到过N皇后问题，你可以看一下，是回溯算法写的：递归问题（二）我先帮你顶一下，看有没有人今晚能帮你看下，不行的话明早再来给你解释下...

Answer 2

package javabase;/**
 * <p>Title: </p>
 *
 * <p>Description: JAVA基础算法</p>
 *
 * <p>Copyright: Copyright (c) 2009</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
public class Queen {
    // 同栏是否有皇后，1表示没有
    private int[] column;//记录是否列冲突
    // 右上至左下是否有皇后
    private int[] rup;//记录是否从对角线冲突
    // 左上至右下是否有皇后
    private int[] lup;//记录是否主对角线冲突
    // 解答
    private int[] queen;
    // 解答编号
    private int num;    public Queen() {
        column = new int[8 + 1];
        rup = new int[2 * 8 + 1];//左上至右下一共有15条对角线，这里应该是把0行0列不计算在内
        lup = new int[2 * 8 + 1];//同上
        
        for (int i = 1; i <= 8; i++) {
            column[i] = 1;//把记录列冲突的数组初始化
        }
        for (int i = 1; i <= 2 * 8; i++) {
            rup[i] = lup[i] = 1;//同上
        }
        queen = new int[8 + 1];
    }    public void backtrack(int i) {
        if (i > 8) {
            showAnswer();
        } else {
            for (int j = 1; j <= 8; j++) {
                if (column[j] == 1 && rup[i + j] == 1 && lup[i - j + 8] == 1) {//如果当前位置没有冲突
                    queen[i] = j; // 设定为占用
                    column[j] = rup[i + j] = lup[i - j + 8] = 0;//然后把对应的记录冲突位置的数组的值设为0
                    backtrack(i + 1);//放完上一行后，放下一行
                    column[j] = rup[i + j] = lup[i - j + 8] = 1;//如果当前行的所有位置都冲突，那么就把上一行的皇后向右移动一个位置
                }
            }
        }
    }    protected void showAnswer() {
        num++;
        System.out.println("\n解答 " + num);
        for (int y = 1; y <= 8; y++) {
            for (int x = 1; x <= 8; x++) {
                if (queen[y] == x) {
                    System.out.print("  Q");
                } else {
                    System.out.print("  .");
                }
            }
            System.out.println();
        }
    }    public static void main(String[] args) {
        Queen queen = new Queen();
        queen.backtrack(1);//从第一行开始放，放完第一行放第二行，依次到最后一行
    }
}
大致的思路是：设置三个数组，分别用来记录列冲突、主对角线冲突和从对角线冲突，用回溯法，先放第一行的皇后，然后行数加1，放第二行，放第二行的皇后的时候，要判断是否列冲突、主对角线冲突和从对角线冲突，如果不冲突就放在当前位置，并在记录列冲突、主对角线冲突和从对角线冲突的这三个数组中的设置相应的值，这里是0（0表示放有皇后，1表示没放），然后继续放下一行的皇后；如果当前行的所有位置都产生冲突，那么就要把当前行的上一行的皇后向右移动一个位置，然后再放当前行的皇后，如果还不行的话，继续向右移动，甚至要移动当前行的上上一行的皇后，以此类推。
不知道这样解释楼主是否能明白，可能有点啰嗦了，见谅