美文网首页
八皇后问题

八皇后问题

作者: Ethan_Walker | 来源:发表于2018-07-28 20:32 被阅读16次

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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
    

    相关文章

      网友评论

          本文标题:八皇后问题

          本文链接:https://www.haomeiwen.com/subject/klfamftx.html