八皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型案例。該問(wèn)題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后，有多種計(jì)算機(jī)語(yǔ)言可以解決此問(wèn)題。

import java.util.ArrayDeque;

/**
 * 任意兩個(gè)皇后不能在同一行、同一列、同一斜線上
 * Created by lenovo on 2018/7/28.
 */
public class Queen {

    static int n; // 皇后數(shù)量，即棋盤的 長(zhǎng)寬

    static boolean[] visitedColumn;   // visitedColumn[0] = true, 表示第 0 列已被訪問(wèn)過(guò) ， 保證各皇后不在同一列
    static int[] rowColumn; // rowColumn[i] = j  表示第 i 行的皇后在第 j 列

    static int count = 0;
    static ArrayDeque<String> stack = new ArrayDeque<>();


    static boolean dfs(int x) {
        // x 表示 第 x 行
        if (x == n) return true;

        for (int y = 0; y < n; y++) {
            // y 代表 第 y 列，對(duì)第 y 列 進(jìn)行試探
            if (visitedColumn[y] == false && isNotDuijiao(x, y)) {
                // 未訪問(wèn)過(guò)的列 & 列 != 已經(jīng)放置的皇后的斜線上, 滿足條件

                visitedColumn[y] = true;
                rowColumn[x] = y;
                stack.push("(" + x + "," + y + ")");


                if (dfs(x + 1)) {
                    // 遞歸試探下一行, 如果最終返回 true ，表示得到正確結(jié)果，逆向打印棧中路徑
                    printStack();
                    count++;
                }

                //  回退
                visitedColumn[y] = false;
                stack.pop();

            }
            // 繼續(xù)試探下一列
        }
        // 執(zhí)行到這一步，表示 第 x 行所有的列試探結(jié)束，返回false
        return false;
    }

    /**
     * 判斷試探的坐標(biāo) x,y 和 x 行之前排布的皇后是否成對(duì)角線
     *
     * @param x
     * @param y
     * @return
     */
    private static boolean isNotDuijiao(int x, int y) {
        int j = 0;
        for (int i = 0; i < x; i++) {
            j = rowColumn[i];
            if (x - i == y - j || (x - i + y - j) == 0) return false; // 是對(duì)角線，返回 false
        }
        return true;
    }

    // 雙棧打印路徑
    private static void printStack() {
        ArrayDeque<String> tempStack = new ArrayDeque<>();
        while (!stack.isEmpty()) {
            tempStack.push(stack.pop());
        }
        while (!tempStack.isEmpty()) {
            String pop = tempStack.pop();
            System.out.print(pop + "——>");
            stack.push(pop);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        n = 8;
        visitedColumn = new boolean[n];
        rowColumn = new int[n];
        for (int i = 0; i < n; i++) {
            visitedColumn[i] = false;
        }

        dfs(0);
        System.out.println(count);
    }
}

輸出

(0,6)——>(1,1)——>(2,5)——>(3,2)——>(4,0)——>(5,3)——>(6,7)——>(7,4)——>
(0,6)——>(1,2)——>(2,0)——>(3,5)——>(4,7)——>(5,4)——>(6,1)——>(7,3)——>
(0,6)——>(1,2)——>(2,7)——>(3,1)——>(4,4)——>(5,0)——>(6,5)——>(7,3)——>
(0,6)——>(1,3)——>(2,1)——>(3,4)——>(4,7)——>(5,0)——>(6,2)——>(7,5)——>
(0,6)——>(1,3)——>(2,1)——>(3,7)——>(4,5)——>(5,0)——>(6,2)——>(7,4)——>
(0,6)——>(1,4)——>(2,2)——>(3,0)——>(4,5)——>(5,7)——>(6,1)——>(7,3)——>
(0,7)——>(1,1)——>(2,3)——>(3,0)——>(4,6)——>(5,4)——>(6,2)——>(7,5)——>
(0,7)——>(1,1)——>(2,4)——>(3,2)——>(4,0)——>(5,6)——>(6,3)——>(7,5)——>
(0,7)——>(1,2)——>(2,0)——>(3,5)——>(4,1)——>(5,4)——>(6,6)——>(7,3)——>
(0,7)——>(1,3)——>(2,0)——>(3,2)——>(4,5)——>(5,1)——>(6,6)——>(7,4)——>
92