This is a crude brute force method starting in the opposite direction, i.e. from the allowed figure eight puzzle. This will allow us to find a bunch of viable solutions.
The brute force method for moving from one super-sine to a potentially 8 seems especially difficult due to the knight's bypass. Based on the runs, about 60% of the viable paths for normal queens are invalid with superqueens. Therefore, if we instead used the brute forces of ordinary queens and then worked in the opposite direction, this is a potential time to find a solution, and we can better determine the lead time. Because we know that normal ladies are easier.
We will start with 12 fundamental solutions, and we will use them as input. The solution to ordinary queens is beyond this, but there is a fantastic article on the wiki page describing everything.
In my case, I saved them as Lines representing the coordinate of the queen (rows are indices).
So: "17468253" = A1, B7, C4, D6, E8, F2, G5, H3
By pushing the opposite direction from the decided queen, we need to test a maximum of 12 x 8! possible solutions. Since order does not matter, further optimization is possible by eliminating duplicate boards and processing solutions.
First up, checkKnight, which seems to be a source of confusion. Using absolute values, you can intelligently determine if a unit is within the range of the knights by checking if the offset X is equal to 2 and the offset Y is 1 or vice versa. You made the sophisticated checkKnight function to check each individual location and regardless of whether the fragment is on the border. Working with a different path, showing each queen to each other queens, is logically simpler and less of a nightmare for debugging.
Queen class
public class Queen { int i, j; public Queen(int i, int j) { this.i = i; this.j = j; } public boolean checkKnight(Queen queen) {
This board has been modified since my publication. It takes a String input and converts it into a complete chessboard. This has little work on a potential board of any size, but right now it is working on creating a daughter board. When a daughterboard is created, queens are passed by reference, rather than creating an entirely new set of queens. A total of 96 queens are stored in memory, 1 for each of the 12-card solutions. Not perfectly optimized, but better 96 → 672 → 4032 → ...
Board Class
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[qi][qj] = 'Q'; } s += " ABCDEFGH\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; } }
Testing class
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); } } }
Final conclusion:
The maximum number of super-queens is: 6 ABCDEFGH 8|Q|_|_|_|_|_|_|_| 7|_|_|_|_|_|_|Q|_| 6|_|_|_|Q|_|_|_|_| 5|_|_|_|_|_|_|_|_| 4|_|_|_|_|_|_|_|Q| 3|_|Q|_|_|_|_|_|_| 2|_|_|_|_|Q|_|_|_| 1|_|_|_|_|_|_|_|_| ABCDEFGH 8|Q|_|_|_|_|_|_|_| 7|_|_|_|_|_|_|_|_| 6|_|_|_|_|Q|_|_|_| 5|_|_|_|_|_|_|_|Q| 4|_|Q|_|_|_|_|_|_| 3|_|_|_|_|_|_|_|_| 2|_|_|_|_|_|Q|_|_| 1|_|_|Q|_|_|_|_|_| ABCDEFGH 8|_|_|_|_|Q|_|_|_| 7|Q|_|_|_|_|_|_|_| 6|_|_|_|_|_|_|_|Q| 5|_|_|_|Q|_|_|_|_| 4|_|_|_|_|_|_|_|_| 3|_|_|_|_|_|_|_|_| 2|_|_|Q|_|_|_|_|_| 1|_|_|_|_|_|Q|_|_| ABCDEFGH 8|_|_|_|_|Q|_|_|_| 7|Q|_|_|_|_|_|_|_| 6|_|_|_|_|_|_|_|Q| 5|_|_|_|Q|_|_|_|_| 4|_|_|_|_|_|_|_|_| 3|_|_|_|_|_|_|Q|_| 2|_|_|Q|_|_|_|_|_| 1|_|_|_|_|_|_|_|_| ABCDEFGH 8|_|_|_|_|Q|_|_|_| 7|Q|_|_|_|_|_|_|_| 6|_|_|_|_|_|_|_|Q| 5|_|_|_|_|_|_|_|_| 4|_|_|Q|_|_|_|_|_| 3|_|_|_|_|_|_|Q|_| 2|_|_|_|_|_|_|_|_| 1|_|_|_|Q|_|_|_|_|
I removed duplicates and made a good way to print boards. I don’t remember the exact mathematics, but this indicates 40 possible places. There are others just by looking, but we have already found a fair chunk! From here we can gently move individual queens around. With a cursory glance, there is one piece on each board that can be transferred to 3 additional spaces, so now we know that there are probably about 160 solutions.
conclusions
In this application, the runtime on my machine was less than a second, which means that if we tie it to the standard applications for queens, additional knight-forcing will not affect this process and the execution time will be almost the same. In addition, since only 6-piece puzzles are possible, we know that your possible launch of the application will complete its detection in 6th place, because there will be no more solutions, since there are no viable solutions of 7 items and 8 items.
In other words, finding the maximum layout of a super queen is likely to be shorter than the maximum layout of a queen due to additional restrictions!