java - 带有一维数组的 Java 中的 N 皇后拼图

Question

我正在解决一个在新手程序员中似乎有点出名的问题，即 8 皇后难题。我已经看到使用二维数组、递归等解决此问题的几种方法，但此问题是 CS 类(class)书籍章节中介绍一维数组的作业，因此解决此问题的可用技术是有限的。

我使用的程序是首先创建一个大小为 64 的一维数组，这使得放置皇后的位置从索引 0 到 63 成为可能。然后生成随机位置索引，并执行测试以检查如果有皇后攻击这个位置。如果这个位置没有被任何皇后攻击，则通过设置 board[position] = true 放置一个皇后。放置皇后后，queenCount 递增，重复此过程，直到放置了 8 个皇后。

如果皇后的放置方式无法放置 8 个，棋盘会在 1 毫秒后通过执行时间检查重置，并重试放置 8 个皇后。最多我可以放置 7 个皇后，但最后一个永远不会放置。每次尝试都会打印出来，连同这次尝试的 queenCount。是否可以使用这种方法，还是死路一条？

下面的代码示例:

package ch7;

public class Chapter_07_E22_EightQueens64bool {

    public static void main(String[] args) {

        int queenCount = 0;
        int attemptCount = 0;
        boolean[] board = new boolean[8 * 8];
        final long TIME_LIMIT = 1; //Milliseconds

        long startTime = System.currentTimeMillis();
        while (queenCount < 8) {

                int position = placeQueen(board.length);

                if(checkPosition(position, board) && !board[position]) {
                    board[position] = true;
                    queenCount++;
                }

                long timeCheck = System.currentTimeMillis();
                if (timeCheck - startTime > TIME_LIMIT) {
                    clearBoard(board);
                    queenCount = 0;
                    startTime = System.currentTimeMillis();
                }         
            System.out.println("Attempt #" + ++attemptCount);
            System.out.println(queenCount + " queens placed.");
            printBoard(board);
        }   
    }      

    public static void printBoard(boolean[] board) {

        for (int i = 0; i < board.length; i++) {

            if (board[i])
                System.out.print("|Q");
            else
                System.out.print("| ");

            if ((i + 1) % 8 == 0)
                System.out.println("|");    
        }
    }

    public static int placeQueen(int boardSize) {
        return (int)(Math.random() * boardSize);
    } 

    public static boolean[] clearBoard(boolean[] board) {

        for (int i = 0; i < board.length; i++)
            board[i] = false;

        return board;

    }

    public static boolean checkPosition(int position, boolean[] board) {

        return checkTop(position, board) && checkBottom(position, board) && checkLeft(position, board) &&
               checkRight(position, board) && checkTopLeft(position, board) && checkTopRight(position, board) &&
               checkBottomLeft(position, board) && checkBottomRight(position, board);
    }

    public static boolean checkTop(int position, boolean[] board) {
        // Checks each field above the current position while i >= 8  
        for (int i = position; i >= 8; i -= 8) {
            if (board[i - 8])
                    return false;  
        }
        return true;                
    }

    public static boolean checkBottom(int position, boolean[] board) {
        // Checks each field below the current position while i <= 55;
        for (int i = position; i <= 55; i += 8) {
            if (board[i + 8])
                    return false;
        }
        return true;                
    }

    public static boolean checkRight(int position, boolean[] board) {
        // Checks each field to the right of the current position while i % 8 < 7
        for (int i = position; i % 8 < 7; i += 1) {
            if (board[i + 1])
                return false;

        }
        return true;                
    }

    public static boolean checkLeft(int position, boolean[] board) {
        // Checks each field to the left of the current position while i % 8 != 0
        for (int i = position; i % 8 != 0; i -= 1) {
            if (board[i - 1])
                return false;  
        }
        return true;                
    }

    public static boolean checkTopLeft(int position, boolean[] board) {
        // Checks each field top left of the current position while i >= 9
        for (int i = position; i >= 9; i -= 9) {
            if (board[i - 9])
                return false;   
        }
        return true;                
    }

    public static boolean checkTopRight(int position, boolean[] board) {
        // Checks each field top right of the current position while i >= 7   
        for (int i = position; i >= 7; i -= 7) {
            if (board[i - 7])
                return false;   
        }
        return true;                
    }

    public static boolean checkBottomRight(int position, boolean[] board) {
        // Checks each field below the current position while i <= 54
        for (int i = position; i <= 54; i += 9) {
            if (board[i + 9])
                return false;    
        }
        return true;                
    }

    public static boolean checkBottomLeft(int position, boolean[] board) {
        // Checks each field below the current position while i <= 56
        for (int i = position; i <= 56; i += 7) {
            if (board[i + 7])
                return false;   
        }
        return true;                
    }

}

Answer 1

首先，大小为 8 的数组就足够了。
数组 index 表示放置皇后的列，value 表示行。

[0, 2, 4, 6, 1, 3, 5, 7] 

意味着第一列的皇后被放在第一行，第二个皇后被放在第三行，第三个皇后被放在第五行，等等......

所以当你放置一个新皇后时，检查你添加它的行是否已经在数组中。这样，您只需要担心对角线碰撞。

解决问题的最简单方法是递归(回溯)。如果不允许，您可以使用堆栈 模拟递归。如果这也不允许，您可以使用 8 个嵌套循环 - 丑陋。

---

您可以使用一个简单的技巧来改进碰撞检查。它是这样工作的-
假设您的 0 号皇后在第 3 行。
她斜向攻击哪些细胞？
在第一列，它是第 2 行和第 4 行(-1 和 +1)
在第二列，它是第 1 行和第 5 行(-2 和 +2)
第三列是第 0 行和第 6 行(-3 和 +3)
所以当你添加一个新的皇后时，你会迭代以前的皇后检查一个对角线 (newIndex - oldIndex) + oldRow == newRow 和另一个对角线 (newIndex - oldIndex) - oldRow ==新行

所以，考虑到所有这些，检查函数可能看起来像

boolean canAdd(List<Integer> p, int newRow) {
    if (p.contains(newRow))
        return false;
    int insertIndex = p.size();
    for (int i = 0; i < p.size(); i++) {
        if (p.get(i) + (insertIndex - i) == newRow || p.get(i) - (insertIndex - i) == newRow)
            return false;
    }
    return true;
}

虽然主要的递归函数看起来像

void solve(List<Integer> p, int index) {
    if (index == 8) {
        System.out.println(p);
        return;
    }

    for (int i = 0; i < 8; i++) {
        if (canAdd(p, i)) {
            p.add(i);
            solve(p, index + 1);
            p.remove(p.size() - 1);
        }
    }
}

你可以这样调用它

solve(new ArrayList<Integer>(), 0);