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算法查找所有骑士位置,是不是错了？或者有一些编码错误.当我注释掉它时,一切正常,我得到了一个很好的解决方案.
>其次它只会产生一个解决方案.对于其他解决方案,我必须在每个mega循环之后逐位偏移(或改变位置)其他部分,我对实现它感到困惑.我的直觉指导我,我需要改变整个代码.有修改或方法吗？
另外的想法：我想我们每次放置一个片段并添加到一个长数组并在存储相关数据后输出最大值和数组时我们会添加一个计数器.
代码位置：您可以在http://ideone.com/gChD8a查看/编辑/分叉/下载它
解决方法
由于骑士的遍历,从单个超级变为潜在的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 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件解决方案.
换句话说,由于额外的限制,找到最大的超级女王布局实际上可能比最大女王布局更短！