一维数组 Java 中的 N 皇后拼图

Question

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

我使用的程序是首先创建一个大小为 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

checkTop 方法中存在一个问题，但可能还有更多问题。

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

有些情况下方法找不到插槽 (board[i - 8] = true) 并且 i 达到 7 的值。在这一点之后，for loop (i > (i - 8)) 的条件将始终为 true 而循环内最外层 if 的条件 (if ( (i - 8) > -1) 将永远是 false。这导致程序无限地停留在循环中。

示例（i 达到-5）：

i = -5;
i > ( i - 8) :  -5 > (-5 -8 = -13) (always true) 
(i - 8) > -1 :  -13 > -1           (false) always false for i <= 7

Answer 2

首先，大小为 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 == newRow

检查另一个对角线

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

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);

Answer 3

在处理这个问题几天后，我现在有了一个解决方案，可以在 N <= 20 的合理时间内运行。它是这样的。

For i < N，初始化queens[i] = i。每行只能包含 1 个值，因此无需检查左侧或右侧的碰撞。只要数组中没有重复值，也不会发生任何列冲突。
使用该方法检查给定点的皇后是否与另一个给定点的皇后共享对角线。该方法检查 x1 和 x0 之间的距离是否等于 y1 和 y0 的距离。如果距离相等，则坐标 (x0,y0) 和 (x1,y1) 共享同一对角线。
使用另一种方法调用 shareDiagonal(int x0, int y0, int x1, int y1) 来检查给定行（例如第 7 行）的皇后是否与第 7 行以上任何行的皇后发生碰撞。如前所述，仅检查给定行上方的行。原因是，例如，如果您正在检查 row2 是否有任何对角线冲突，则在检查具有更高索引值的行时，将显示与第 2 行以下的行的任何冲突。如果第 2 行的女王与第 4 行的女王发生碰撞，这将在检查第 4 行和上面的行时显示出来。
第三种检查方法调用checkRowForCollision(int[] queens, int row)，其中遍历每一行检查上面行的冲突。检查第 1 行是否与第 0 行的皇后有任何碰撞，检查第 2 行的第 0 行和第 1 行是否有任何碰撞，检查第 3 行的第 0、1 和 2 行是否有任何碰撞，等等。
当任何皇后之间发生对角线碰撞时，棋盘会洗牌，直到显示出没有皇后互相攻击的解决方案。

下面的代码示例：

package ch7;

public class Chapter_07_E22_EightQueens {

    static final int N = 8;

    public static void main(String[] args) {

        int[] queens = new int[N];
        int attempts = 0;

        for (int i = 0; i < N; i++) 
            queens[i] = i;

        while (checkBoardForCollision(queens)) {
            shuffleBoard(queens);
            attempts++;
        }
        printBoard(queens);
        System.out.println("Solution found in " + attempts + " attempts");
    }

    public static void printBoard(int[] queens) {

        for (int row = 0; row < N; row++) {
            System.out.printf("%-1c", '|');
            for (int column = 0; column < N; column++) {
                System.out.printf("%-1c|", (queens[row] == column) ? 'Q' : ' ');
            }
            System.out.println();
        }       
    }

    public static boolean shareDiagonal(int x0, int y0, int x1, int y1) {

        int dy = Math.abs(y1 - y0);
        int dx = Math.abs(x1 - x0);

        return dx == dy;
    }

    public static boolean checkRowForCollision(int[] queens, int row) {

        for (int i = 0; i < row; i++) {

            if (shareDiagonal(i, queens[i], row, queens[row]))
                return true;    
        }
        return false;
    }

    public static boolean checkBoardForCollision(int[] queens) {

        for (int row = 0; row < queens.length; row++)
            if (checkRowForCollision(queens, row))
                return true;

        return false;
    }

    public static int[] shuffleBoard(int[] queens) {

        for (int i = queens.length - 1;  i > 0; i--) {

            int j = (int)(Math.random() * (i + 1));

            int temp = queens[i];
            queens[i] = queens[j];
            queens[j] = temp;
        }
        return queens;
    }
}

一维数组 Java 中的 N 皇后拼图

N-queens puzzle in Java with 1D array

java

arrays

n-queens