java - 对编写将一些修改后的皇后型棋子放在 8 x 8 棋盘上的程序感到困惑

Question

对于这个问题:

The superqueen is a chess piece that can move like a queen, but also like a knight. What is the maximal number of superqueens on an 8X8 chessboard such that no one can capture an other?

我想写一个蛮力算法来找到最大值。这是我写的:

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 算法会查找所有骑士位置，这是错误的吗？或者有一些编码错误。当我注释掉它时一切正常，我得到了一个很好的解决方案。
• 其次，它只会产生一个解决方案。对于其他解决方案，我必须在每个大型循环之后一点一点地偏移(或更改位置)其他部分，我对实现它感到困惑。我的直觉引导我需要更改整个代码。有修改或方法吗？

额外的想法:我认为我们会在每次放置一 block 时添加一个计数器并添加到一个长数组并在存储相关数据后输出最大值和数组。

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

Answer 1

这是一种粗略的蛮力方法，从相反的方向开始，即从已解决的八皇后难题开始。这将使我们能够找到一系列可行的解决方案。

由于马的遍历，从单个 super 女王到可能 8 的蛮力技术似乎特别复杂。根据运行，大约 60% 的普通皇后的可行路径对 super 皇后无效。因此，如果我们改为暴力破解普通皇后，然后逆向计算，这可能会节省寻找解决方案的时间，而且我们可以更好地确定运行时间。因为我们知道普通皇后更容易。

我们从 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 板解决方案中，每个皇后 1 个。没有完美优化，但优于 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 个可能的位置。还有其他的，只是通过观察，但我们已经找到了相当大的一部分!从这里，我们可以轻轻地移动个别皇后。粗略地看，每 block 板都有一 block 可以移动到 3 个额外的空间，所以现在我们知道大约有 160 种解决方案。

结论

有了这个应用程序，我机器上的运行时间不到一秒，这意味着如果我们将它附加到一个标准的皇后应用程序，额外的骑士的暴力破解将不会对该过程产生影响并且几乎相同运行。此外，因为只有 6 block 拼图是可能的，我们知道您最终的应用程序运行将在放置的第 6 block 拼图处完成查找，因为没有更多的解决方案是可能的，因为没有可行的 7 block 和 8 block 解决方案.

换句话说，由于额外的限制，寻找最大 super 皇后布局实际上可能比最大皇后布局更短!