对于编写一个程序，在8 x 8棋盘上放置一些修改后的皇后型棋子感到困惑

Question

对于这个问题：

超级皇后是一种象棋棋子，可以像皇后一样移动，但也可以像骑士一样移动。在一个8X8的棋盘上，最多可以放置多少个超级皇后，以使得没有一个超级皇后被其他人攻击？

我想编写一个暴力算法来找到最大值。以下是我的代码：

public class Main {

    public static boolean chess[][];

    public static void main(String[] args) throws java.lang.Exception {
        chess = new boolean[8][8];
        chess[0][0] = true;

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                /*Loop to check various possibilities*/
                if (!checkrow(i) && !checkcolumn(j) && !checkdiagonals(i, j) && !checkknight(i, j)) {
                    if (i != 0 || j != 0) {
                        chess[i][j] = true;
                    }
                }
            }
        }/*printing the array*/

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                System.out.print(((chess[i][j]) ? "T" : "x") + "|");
            }
            System.out.println();
        }
    }

    /*All working fine here*/
    public static boolean checkrow(int a) {

        for (int i = 0; i < 8; i++) {
            if (chess[a][i]) {
                return true;
            }
        }
        return false;
    }

    /*All working fine here*/
    public static boolean checkcolumn(int a) {

        for (int i = 0; i < 8; i++) {
            if (chess[i][a]) {
                return true;
            }
        }
        return false;
    }

    /*All working fine here*/
    public static boolean checkdiagonals(int pi, int pj) {

        int i = pi - Math.min(pi, pj);
        int j = pj - Math.min(pi, pj);

        for (int k = i, l = j; k < 8 && l < 8; k++, l++) {
            if (chess[k][l]) {
                return true;
            }
        }

        int i_2 = pi - Math.min(pi, pj);
        int j_2 = pj + Math.min(pi, pj);

        for (int k = i_2, l = j_2; k < 8 && l > 1; k++, l--) {
            if (chess[k][l]) {
                return true;
            }
        }
        return false;
    }

    /*Not All working fine here try commenting out this method above so that that it doesn't run during the check*/
    public static boolean checkknight(int pi, int pj) {

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (0 <= pi + 2 * i && pi + 2 * i <= 8 && 0 <= pj + j && pj + j <= 8) {
                    if (chess[pi + 2 * i][pj + j]) {
                        return true;
                    }
                }

                if (0 <= pi + i && pi + i <= 8 && 0 <= pj + 2 * j && pj + 2 * j <= 8) {
                    if (chess[pi + i][pj + 2 * i]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

我有两个问题：

• 我的checkknight算法查找所有马的位置，这是错误的吗？还是有一些编码错误。当我注释掉它时，一切都正常工作，我得到了一个很好的解决方案。
• 其次，它只会导致一个解决方案。对于其他解决方案，我必须在每个大循环之后逐位偏移（或更改位置）其他部分，我对实现它感到困惑。我的直觉告诉我，我需要改变整个代码。是否有修改或方法可以做到这一点？

其他想法：我认为每次放置一个棋子时，我们应该将计数器加1，并添加到长数组中，并在存储相关数据后输出最大值和数组。

代码位置：您可以在http://ideone.com/gChD8a查看/编辑/派生/下载它。

- RE60K

---

你可以在互联网上搜索建议，以找到最佳解决方法。此外，你需要使用递归来解决这个问题。第三，你的问题对于这个论坛来说太宽泛了。你需要提出具体的问题，以便得到明确的答案。 - ControlAltDel

测试 <=8 看起来有点可疑。它们不应该是 <8 吗？ - David Eisenstat

@DavidEisenstat也许你是对的，因为这是一个8x8的数组，所以最大值是i=7？ - RE60K

是的，如果您尝试访问一个包含8个元素的数组中的第8个元素，将会引发异常。 - David Eisenstat

我对此很感兴趣。出于好奇，您是否考虑过从标准的8Q Puzzle反向工作？如果您从经典的8Q 12个解开始，可以非常快速地覆盖所有情况（12个解，8个皇后要移除= 96个棋盘，其中7个皇后，672个棋盘有6个皇后（其中至少一个是解决方案），等等。如果可以的话，我稍后可以写一个演示文稿。根据我所知，这种暴力破解方法需要大量操作。 - Compass

暴力算法很简单。将皇后添加到棋盘上的一个空格中，从考虑范围中删除她可以攻击到的所有空格。在第一个空位上向棋盘添加下一个皇后，并重复此过程。当您无法再添加任何皇后时，因为没有空间可放置它们，请尝试将您最后放置的皇后移动到下一个有效空间。当第一位皇后已经放置在左上象限的每个空间中时，计算出您的最大值（由于棋盘两侧对称，我们只需要计算其中的四分之一）。 - Steve K

Answer 1

这是一种从相反方向开始的粗暴的暴力方法，即从解决八皇后问题开始。这将使我们能够找到一堆可行的解决方案。

由于骑士的遍历方式，从单个超级皇后到潜在的8个皇后的暴力技术似乎特别复杂。根据运行结果，对于普通皇后的大约60％的可行路径对于超级皇后来说无效。因此，如果我们改为暴力破解普通皇后，然后再往回推，那么就有可能节省寻找解决方案的时间，并且我们可以更好地确定运行时间。因为我们知道普通皇后比较容易。

我们从12个基本解开始，然后将它们用作输入。解决普通皇后不在此范围内，但维基页面有一篇描述一切的绝妙文章。

在我的情况下，我将它们存储为表示皇后坐标的字符串（行是索引）。

因此："17468253" = A1，B7，C4，D6，E8，F2，G5，H3

通过从已解决的皇后开始粗暴地破解相反的方向，我们最多只需要测试12 x 8！个可能的解决方案。因为顺序无关紧要，通过消除重复的棋盘和解决方案进行额外的优化可以发生。

首先是检查骑士的checkKnight函数，这似乎让您感到困惑。使用绝对值，您可以合理地确定一件物品是否在骑士的范围内，方法是检查X偏移量是否为2而Y偏移量是否为1，或者反之亦然。您制作了一个复杂的checkKnight函数，以检查每个单独的位置和一个棋子是否在边界上。通过逐个检查每个皇后是否与其他皇后相撞的方式更简单，并且更不容易出错。

皇后类

public class Queen {
    int i, j;

    public Queen(int i, int j) {
        this.i = i;
        this.j = j;
    }

    public boolean checkKnight(Queen queen) { // if any queen meets another
                                                // queen at 2 and 1 offset, we
                                                // eliminate it.
        return (Math.abs(i - queen.i) == 2 && Math.abs(j - queen.j) == 1)
                || (Math.abs(i - queen.i) == 1 && Math.abs(j - queen.j) == 2);
    }
}

自我最初发布以来，这个板子已经进行了修改。它接受一个字符串输入并将其转换为完整的棋盘。它对于任意大小的棋盘有一些小工作，但现在它处理子棋盘的创建。当创建子棋盘时，皇后通过引用传递而不是制作一个全新的皇后集合。总共存储了96个皇后在内存中，每个皇后都在原始12个棋盘解决方案中占据一个位置。虽然不是完美优化，但比96 -> 672 -> 4032 -> ...更好。

棋盘类

public class Board {
    static int boardSize = 8;
    ArrayList<Queen> queens = new ArrayList<Queen>();

    public Board(String s) {
        for (int i = 0; i < s.length(); i++) {
            queens.add(new Queen(i, s.charAt(i) - 49)); // you could implement
                                                        // base 16 here, for
                                                        // example, for a 15x15
                                                        // board
        }
    }

    public Board(Board b) { // duplicates the board, but keeps references to
                            // queens to conserve memory, only 96 total queens
                            // in existence through search!
        for (Queen q : b.queens) {
            queens.add(q);
        }
    }

    public boolean checkForImpact() {
        for (int i = 0; i < queens.size(); i++) {
            for (int j = i + 1; j < queens.size(); j++) {
                if (queens.get(i).checkKnight(queens.get(j))) { // just check
                                                                // for any
                                                                // queens
                                                                // intersecting,
                                                                // one hit is
                                                                // enough
                    return true;
                }
            }
        }
        return false;
    }

    public ArrayList<Board> getChildBoards() { // create child boards with a
                                                // single queen removed
        ArrayList<Board> boards = new ArrayList<Board>();
        for (int i = 0; i < queens.size(); i++) {
            boards.add(new Board(this));
        }
        int i = 0;
        for (Board b : boards) {
            b.queens.remove(i);
            i++;
        }
        return boards;
    }

    public String drawBoard() {
        String s = "";
        char[][] printableBoard = new char[boardSize][boardSize];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                printableBoard[i][j] = '_';
            }
        }
        for (Queen q : queens) {
            printableBoard[q.i][q.j] = 'Q';
        }
        s += "  A B C D E F G H\n";
        for (int i = 0; i < 8; i++) {
            s += (8 - i) + "|";
            for (int j = 0; j < boardSize; j++) {
                s += printableBoard[i][j];
                s += "|";
            }
            s += "\n";
        }
        return s;
    }
}

测试类

import java.util.ArrayList;

public class Test {
    static String[] boards = { "24683175", "17468253", "17582463", "41582736",
            "51842736", "31758246", "51468273", "71386425", "51863724",
            "57142863", "63184275", "53172864" }; // all 12 solutions for the 8
                                                    // queens problem
    static ArrayList<Board> boardObjects = new ArrayList<Board>();

    public static void main(String[] args) {
        for (String queens : boards) { // create starter boards
            boardObjects.add(new Board(queens));
        }

        int i;
        ArrayList<Board> foundBoards = null;
        for (i = 8; i > 0; i--) {
            ArrayList<Board> newBoards = new ArrayList<Board>();
            foundBoards = new ArrayList<Board>();
            for (Board b : boardObjects) {
                if (b.checkForImpact()) { // if any queen intercepts we get
                                            // children
                    ArrayList<Board> boardsToBeAdded = b.getChildBoards(); // pass
                                                                            // all
                                                                            // permutations
                                                                            // of
                                                                            // queens
                                                                            // once
                                                                            // removed
                    for (Board bo : boardsToBeAdded) {
                        newBoards.add(bo); // add it in to the next list
                    }
                } else {
                    foundBoards.add(b); // if we have no impact, we have a
                                        // solution
                }
            }
            if (!foundBoards.isEmpty())
                break;
            boardObjects.clear();
            boardObjects = newBoards;
        }
        System.out.println("The maximum number of super-queens is: " + i);
        ArrayList<String> winningCombinations = new ArrayList<String>();
        for (Board board : foundBoards) {
            String createdBoard = board.drawBoard();
            boolean found = false;
            for (String storedBoard : winningCombinations) {
                if (storedBoard.equals(createdBoard))
                    found = true;
            }
            if (!found)
                winningCombinations.add(createdBoard);
        }
        for (String board : winningCombinations) {
            System.out.println(board);
        }
    }
}

最终输出结果为：

The maximum number of super-queens is: 6
  A B C D E F G H
8|Q|_|_|_|_|_|_|_|
7|_|_|_|_|_|_|Q|_|
6|_|_|_|Q|_|_|_|_|
5|_|_|_|_|_|_|_|_|
4|_|_|_|_|_|_|_|Q|
3|_|Q|_|_|_|_|_|_|
2|_|_|_|_|Q|_|_|_|
1|_|_|_|_|_|_|_|_|

  A B C D E F G H
8|Q|_|_|_|_|_|_|_|
7|_|_|_|_|_|_|_|_|
6|_|_|_|_|Q|_|_|_|
5|_|_|_|_|_|_|_|Q|
4|_|Q|_|_|_|_|_|_|
3|_|_|_|_|_|_|_|_|
2|_|_|_|_|_|Q|_|_|
1|_|_|Q|_|_|_|_|_|

  A B C D E F G H
8|_|_|_|_|Q|_|_|_|
7|Q|_|_|_|_|_|_|_|
6|_|_|_|_|_|_|_|Q|
5|_|_|_|Q|_|_|_|_|
4|_|_|_|_|_|_|_|_|
3|_|_|_|_|_|_|_|_|
2|_|_|Q|_|_|_|_|_|
1|_|_|_|_|_|Q|_|_|

  A B C D E F G H
8|_|_|_|_|Q|_|_|_|
7|Q|_|_|_|_|_|_|_|
6|_|_|_|_|_|_|_|Q|
5|_|_|_|Q|_|_|_|_|
4|_|_|_|_|_|_|_|_|
3|_|_|_|_|_|_|Q|_|
2|_|_|Q|_|_|_|_|_|
1|_|_|_|_|_|_|_|_|

  A B C D E F G H
8|_|_|_|_|Q|_|_|_|
7|Q|_|_|_|_|_|_|_|
6|_|_|_|_|_|_|_|Q|
5|_|_|_|_|_|_|_|_|
4|_|_|Q|_|_|_|_|_|
3|_|_|_|_|_|_|Q|_|
2|_|_|_|_|_|_|_|_|
1|_|_|_|Q|_|_|_|_|

我已经删除了重复项并制作了一个不错的棋盘打印方法。我不记得确切的数学公式，但这突出显示了40个可能的位置。还有其他的，只要看一眼，但我们已经找到了大量的解决方案！从这里开始，我们可以轻松地移动单个皇后。经过初步查看，每个棋盘都有一个可以移动到3个额外空间的单个棋子，因此现在我们知道可能有大约160种解决方案。

结论

使用此应用程序，在我的机器上运行时间少于一秒钟，这意味着如果我们将其附加到标准皇后应用程序上，则附加骑士的蛮力对该进程没有影响，并且具有几乎相同的运行时间。另外，由于只有6件拼图是可能的，我们知道您最终的应用程序运行将在放置第6件拼图时完成其查找，因为不存在可行的7件和8件拼图方案。

换句话说，由于额外的限制条件，找到最大的超级皇后布局实际上可能比最大的皇后布局更短！

- Compass

Answer 2

尝试暴力解决这样的问题是了解它的好方法。因此，我不建议一开始就查找预先准备好的解决方案。

不过有一点需要注意：我不明白你为什么要设置条件if (i != 0 || j != 0) {。你正在处理Java数组。它们从0到7而不是1到8，但是0是第一列，你不应该将其排除，否则只有一个7x7的棋盘。

首先，让我回答你的技术问题：如何计算马的位置。

拿一张四方格纸，在边缘不少于两个方块的地方放置一个皇后。然后标记从上面移动一个马步所到达的结束位置。

你最终会得到只需考虑8个方块的结果。没有必要使用3x3循环来查找它们。更好的想法是准备一个静态数组，其中包含马跳的相对坐标 - 8对数字的数组 - 并在其中循环。所以你只需要一个8步循环。在循环的每一步中，检查边界（0≤X + Xoffset < 8，0≤Y + Yoffset < 8），然后你就有了马的坐标。

其次，检查在你前面的部分是没有意义的。因为你还没有覆盖下一行和下面的行，所以在那里寻找皇后是没有意义的。这意味着：

- 你永远不会在刚刚标记了皇后位置的同一行放置另一个皇后（因为你在水平方向上威胁它）。这意味着如果你标记了一个皇后，应使用continue跳出内部循环到下一行。 - 你不需要checkrow()。当你开始一行时，你前面没有皇后。如果你遵循了上面的要点，你的背后也没有皇后。 - 当你使用checkcolumn时，你从第0行开始，但是你可以完成在你之前的一行（i-1

但是最重要的是，一旦你完成了并且皇后已经就位并打印棋盘：你将拥有一个解决的棋盘。你已经证明这个皇后数量是可能的。但它是否是可能的最高数量？你还没有检查如果你不在第一行的第一个方格上放置一个皇后，而是放在第二个方格上会发生什么。也许这会让你稍后能够再放一个皇后。那第二行的皇后呢？也许如果你移动它，你就可以把一个皇后放在之前无法放置的下面。

因此，现在你必须实际上再做同样的事情，每次更改一个决策并从那里开始工作。实际上，你有许多潜在的棋盘。为什么呢？因为在你放置该行皇后的每一行中可能有多个有效位置。所以你决定把它放在第一个有效位置。但是如果你决定把它放在第二个有效位置呢？或者空着那一行呢？每个这样的决定都会导致对下一行的另一组决策。

不同的决策创建了不同的棋盘形成一棵决策树。因此，你需要考虑的问题是如何解决这样一棵树。如何编写你的决策线路，然后回溯、更改、填充另一个棋盘并计算每一级的皇后数量。这里的人们建议使用递归，因为它很好地适用于这些问题。或者如果你想的话，可以保持一堆决策。你可以根据对称性消除一些潜在的棋盘。

我建议你首先确保你很好地理解你的单个棋盘，然后考虑如何表示你的决策树以及如何遍历它。

- RealSkeptic

Answer 3

这里有几个问题。

第一个问题是：在nxn的棋盘上最多可以放置多少个骑士皇后？由于k件解决方案可以轻松地降低到k-1件解决方案，因此从上限开始寻找是有意义的。也就是说，先寻找n件解决方案，如果失败了再寻找n-1件解决方案，以此类推。

第二个问题是：如何寻找k件解决方案？有两种经典策略：深度优先和广度优先。前者一次考虑搜索树的一个顶点，并在失败时使用回溯。后者则一次考虑搜索树的一个完整层。

在这里考虑对称性（在本例中为旋转和反射）可以对搜索产生很大的影响。

第三个（隐含的）问题是：这里应该选择什么样的表示方法？如果您的棋盘小于8x8，则64位比特模式非常适用！

实际上，尽可能分离问题的三个层面。如果不这样做，您会发现在一个层面上的选择会严重限制另一个层面的选项。

- Rafe