八皇后问题 java实现，算法两则

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是19世纪著名的数学家高斯1850年提出：在8×8格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。[英国某著名计算机图形图像公司面试题]

算法1：典型的回朔算法。打印出8皇后的最终排列。解析：递归实现n皇后问题。算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列。如果某列上已经有皇后，则为1，否则为0。数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]。如果某条主对角线上已经有皇后，则为1，否则为0。数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]。如果某条从对角线上已经有皇后，则为1，否则为0。

package org.luyang.csdn;

public class EightQueue {    String[][] rec = new String[8][8];

    int[] a = new int[8];

    int[] b = new int[15];

    int[] c = new int[15];

    int sum;

    public EightQueue() {        super();        for (int i = 0; i < this.rec.length; i++) {            for (int j = 0; j < this.rec[i].length; j++) {                this.rec[i][j] = "○";            }        }

    }

    public void prt() {        System.out.println("");        for (int i = 0; i < this.rec.length; i++) {            for (int j = 0; j < this.rec[i].length; j++) {                System.out.print(this.rec[i][j] + " ");            }            System.out.println("");        }

        System.out.println("");    }

    /**     * set the queen of line i     *      * @param i     */    void qu(int i) {        for (int iColumn = 0; iColumn < 8; iColumn++) {            if (a[iColumn] == 0 && b[i - iColumn + 7] == 0                    && c[i + iColumn] == 0) {                // do not conflict                rec[i][iColumn] = "●";                a[iColumn] = 1;                b[i - iColumn + 7] = 1;                c[i + iColumn] = 1;                if (i < 7)                    qu(i + 1);                else {                    // sysout                    prt();                    sum++;                }                // whatever how to put the queen, mission is impossible. rollback                rec[i][iColumn] = "○";                a[iColumn] = 0;                b[i - iColumn + 7] = 0;                c[i + iColumn] = 0;            }        }    }

    /**     * 8 queen     * @param args     */    public static void main(String[] args) {        EightQueue eq = new EightQueue();        eq.qu(0);        System.out.println(eq.sum);    }}

算法2，也不知道是从哪里剽窃过来的了，该算法没有最终答应出排列组合，仅仅给出有多少种组合，但是算法确实十分奥妙，提供出来大家分享。

package org.luyang.csdn;

public class Queen {    static int sum = 0, upperlim = 1;

    private static void test(int row, int ld, int rd) {

        if (row != upperlim) {            int pos = upperlim & ~(row | ld | rd);            while (pos != 0) {                int p = pos & -pos;                pos -= p;                test(row + p, (ld + p) << 1, (rd + p) >> 1);            }        } else            sum++;    }

    public static void main(String[] args) {        int n = 8;

        if (args.length == 1)            n = Integer.parseInt(args[0]);

        long tm = System.currentTimeMillis();        if ((n < 1) || (n > 32)) {            System.out.println(" heh..I can't calculate that.");            System.exit(-1);        }        System.out.println(n + " Queens");        upperlim = (upperlim << n) - 1;

        test(0, 0, 0);        System.out.println("Number of solutions is " + sum + ", "                + (System.currentTimeMillis() - tm) + " milliseconds");    }}