java – 编写一个程序,用于在8 x 8板上放置一些经过修改的大号型

由于骑士的遍历,从单个超级变为潜在的8的蛮力技术似乎特别复杂.根据运行情况,正常女王的大约60％的可行路径对于超级队列是无效的.因此,如果我们反而强迫普通皇后,然后向后工作,那么节省了寻找解决方案的潜在时间,我们可以更好地确定运行时间.因为我们知道普通的皇后更容易.

我们从12个基本解决方案开始,然后我们将这些作为输入.解决普通女王的问题不在此范围内,但维基页面上有一篇很棒的文章描述了一切.

在我的例子中,我将它们存储为表示女王坐标的字符串(行是索引).

所以：“17468253”= A1,B7,C4,D6,E8,F2,G5,H3

通过强制反向解决的皇后,我们只需要测试最多12 x 8！可能的解决方案.由于订单无关紧要,因此可以通过消除重复的电路板和解决方案来进行额外的优化.

首先,checkKnight,这似乎是你的困惑之源.使用绝对值,您可以通过检查X偏移是否为2且Y偏移是否为1来合理地确定一块是否在骑士的范围内,反之亦然.您已经制作了一个复杂的checkKnight功能来检查每个位置以及一块是否在边框上.通过hitscanning每个女王到另一个女王的另一种方式工作在逻辑上更简单,而不是调试的噩梦.

女王班

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

自我最初发布以来,该主板已经过修改.它需要一个String输入并将其转换为完整的棋盘.它对潜在的任何规模的电路板都有一些小的工作,但现在它处理子板的创建.创建子板时,通过引用传递皇后,而不是制作一组全新的皇后.总共有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 Hn";
        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件解决方案.

换句话说,由于额外的限制,找到最大的超级女王布局实际上可能比最大女王布局更短！