Java – I’m confused about writing a program to place some modified large parts on the 8 x 8 board
For this question:
I want to write a powerful algorithm to find the maximum This is what I wrote:
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;
}
}
I have two questions:
>Is my checkknight algorithm wrong to find all Knight positions? Or there are some coding errors When I commented it out, everything was normal and I got a good solution. > Second, it will only produce one solution For other solutions, I have to offset (or change position) other parts bit by bit after each Mega loop, and I'm confused about implementing it My intuition guided me that I needed to change the whole code Is there any modification or method?
Another idea: I think we will add a counter every time we place a fragment and add it to a long array, and output the maximum value and array after storing the relevant data
Code location: you can http://ideone.com/gChD8a View / edit / fork / download it
Solution
This is a rough method of violence, starting in the opposite direction, that is, from the eight queens puzzle This will enable us to find a bunch of feasible solutions
Due to the knight's traversal, the brute force technology from a single super to a potential 8 seems particularly complex According to the operation, about 60% of the feasible paths of the normal queen are invalid for the super queue Therefore, if we instead force the ordinary queen to work backwards, we can save the potential time to find a solution, and we can better determine the running time Because we know that ordinary queens are easier
We start with 12 basic solutions, and then we take these as input Solving the ordinary Queen's problem is not within this scope, but there is a great article on the wiki page that describes everything
In my example, I store them as strings representing Queen's coordinates (rows are indexes)
So: "17468253" = A1, B7, C4, D6, E8, F2, G5, H3
Through the queen of forced reverse solution, we only need to test up to 12 x 8! Possible solutions Since the order is insignificant, additional optimization can be done by eliminating duplicate boards and solutions
First of all, check knight, this seems to be the source of your confusion Using absolute values, you can reasonably determine whether a piece is within the range of a knight by checking whether the X offset is 2 and the Y offset is 1, and vice versa You have created a complex checkknight function to check each position and whether a piece is on the border Another way to work from one queen to another by hitcanning is logically simpler than the nightmare of 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) { // 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);
}
}
Since its initial release, the motherboard has been modified It requires a string input and converts it into a complete chessboard It has some small work for potentially any size board, but now it handles the creation of child boards When creating a child board, the queen is passed by reference instead of making a new set of queens A total of 96 queens are stored in memory, one for each queen in the original 12 board solution No perfect optimization, but better than 96 – > 672 – > 4032 – >
Board course
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;
}
}
Examination 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);
}
}
}
The final output is:
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|_|_|_|_|
I deleted duplicate items and made a beautiful circuit board printing method I don't remember the exact math, but it highlights 40 possible positions There are others, just through observation, but we have found a considerable part! From here, we can gently transfer individual queens From the rough appearance, each board can be moved to 3 additional spaces, so now we know that there may be about 160 solutions
conclusion
With this application, the running time on my machine is less than one second, which means that if we attach it to the standard queen application, the additional Knight's violent coercion will not affect the process, and has almost the same running time In addition, because only 6 pieces of jigsaw puzzle are possible, we know that your final application will be completed in piece 6, because no more solutions are possible, because there are no feasible 7-piece and 8-piece solutions
In other words, due to additional constraints, finding the largest Super Queen layout may actually be shorter than the largest queen layout!