八皇后问题

面试经典 Finley Fu 2020-01-01 142评论 1535
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

   回溯算法  

        这个问题很适合用”回溯算法“解答,下面以四皇后为例看下算法过程

        首先把Q1放入第一行第一个格子,那么Q2就自动排除了红色的格子,还剩两个格子可以放置。

        假如把Q2放入第二行第三个格子,可以看到,第三行已经完全不能再放置了,所以这种方法无解,然后返回重新放置Q2位置。

        把Q2放到第二行第四个格子,那么此时Q3只能放入第三行第二个格子,但是如果这样放置,Q4就没办法再放置,所以只能回溯返回到Q3,但是Q3也无处安置,再回溯到Q2,Q2的位置也被测试完毕,继续回溯到Q1,所以Q1放置到第一行第二个格子,以此类推直到Q1无处安置。最后一共有92种解法。

   java实现  

public class Queen {
    private int[] column; //同栏是否有皇后,1表示有
    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] = 0;
        for (int i = 1; i <= (2*8); i++)
            rup[i] = lup[i] = 0;  //初始定义全部无皇后
        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] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {
                    //若无皇后
                    queen[i] = j; //设定为占用
                    column[j] = rup[i+j] = lup[i-j+8] = 1;
                    backtrack(i+1);  //循环调用
                    column[j] = rup[i+j] = lup[i-j+8] = 0;
                }
            }
        }
    }
 
    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);
    }
}