八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

import java.util.ArrayDeque;

/**
 * 任意两个皇后不能在同一行、同一列、同一斜线上
 * Created by lenovo on 2018/7/28.
 */
public class Queen {

    static int n; // 皇后数量，即棋盘的 长宽

    static boolean[] visitedColumn;   // visitedColumn[0] = true, 表示第 0 列已被访问过 ， 保证各皇后不在同一列
    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 列，对第 y 列 进行试探
            if (visitedColumn[y] == false && isNotDuijiao(x, y)) {
                // 未访问过的列 & 列 != 已经放置的皇后的斜线上, 满足条件

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


                if (dfs(x + 1)) {
                    // 递归试探下一行, 如果最终返回 true ，表示得到正确结果，逆向打印栈中路径
                    printStack();
                    count++;
                }

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

            }
            // 继续试探下一列
        }
        // 执行到这一步，表示 第 x 行所有的列试探结束，返回false
        return false;
    }

    /**
     * 判断试探的坐标 x,y 和 x 行之前排布的皇后是否成对角线
     *
     * @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; // 是对角线，返回 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