java - Confused about writing a program for placing some modified queen-type pieces on an 8 x 8 board -
to question:
the superqueen chess piece can move queen, knight. maximal number of superqueens on 8x8 chessboard such no 1 can capture other?
i want write brute force algorithm find maximum. here's 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; (int = 0; < 8; i++) { (int j = 0; j < 8; j++) { /*loop check various possibilities*/ if (!checkrow(i) && !checkcolumn(j) && !checkdiagonals(i, j) && !checkknight(i, j)) { if (i != 0 || j != 0) { chess[i][j] = true; } } } }/*printing array*/ (int = 0; < 8; i++) { (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) { (int = 0; < 8; i++) { if (chess[a][i]) { return true; } } return false; } /*all working fine here*/ public static boolean checkcolumn(int a) { (int = 0; < 8; i++) { if (chess[i][a]) { return true; } } return false; } /*all working fine here*/ public static boolean checkdiagonals(int pi, int pj) { int = pi - math.min(pi, pj); int j = pj - math.min(pi, pj); (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); (int k = i_2, l = j_2; k < 8 && l > 1; k++, l--) { if (chess[k][l]) { return true; } } return false; } /*not working fine here try commenting out method above that doesn't run during check*/ public static boolean checkknight(int pi, int pj) { (int = -1; <= 1; i++) { (int j = -1; j <= 1; j++) { if (0 <= pi + 2 * && pi + 2 * <= 8 && 0 <= pj + j && pj + j <= 8) { if (chess[pi + 2 * i][pj + j]) { return true; } } if (0 <= pi + && pi + <= 8 && 0 <= pj + 2 * j && pj + 2 * j <= 8) { if (chess[pi + i][pj + 2 * i]) { return true; } } } } return false; } } i have 2 questions:
- my algorithm checkknight looks knight positions, wrong? or there coding error.everything working fine when comment out , nice solution.
- secondly it'll result in 1 solution.for other solutions have offset(or change position) of other pieces bit bit after each mega-loop of this, confused implementing it. instincts guide me need change whole of code. there modification or way it?
additional thoughts: think add counter each time place piece , add long array , output maximum , array after storing relevant data.
code location: may view/edit/fork/download @ http://ideone.com/gchd8a
this rough brute-force method starting opposite direction, i.e. solved eight-queens puzzle. allow find bunch of viable solutions.
the brute-force technique going single superqueen potentially 8 seems complex due knight's traversal. based on runs, 60% of viable paths normal queens invalid superqueens. if instead brute force normal queens, , work backwards, potential time saved finding solution, , can better determine run-time. because know normal queens easier.
we start off 12 fundamental solutions, use these inputs. solving normal queens outside this, wiki page has fantastic article describing everything.
in case, stored them strings representing coordinate of queen (the rows indices).
so: "17468253" = a1, b7, c4, d6, e8, f2, g5, h3
by brute-forcing opposite direction solved queens, have test @ 12 x 8! possible solutions. because order doesn't matter, additional optimization occur eliminating duplicate boards , solutions processing.
first up, checkknight, appears source of confusion. using absolute values, can reasonably determine whether or not piece within knight's range checking whether x offset 2 , y offset 1, or vice versa. you've made complex checkknight function check each individual location , whether or not piece on border. working other way hitscanning each queen each other queen logically simpler , less of nightmare debug.
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 queen meets // queen @ 2 , 1 offset, // 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); } } this board has been modified since posted. takes string input , converts full chessboard. has minor work towards potential any-size board, right handles child board creation. when child board created, queens passed reference rather making whole new set of queens. total of 96 queens stored in memory, 1 each 1 on original 12-board solution. not optimized, better 96 -> 672 -> 4032 -> ...
board class
public class board { static int boardsize = 8; arraylist<queen> queens = new arraylist<queen>(); public board(string s) { (int = 0; < s.length(); i++) { queens.add(new queen(i, s.charat(i) - 49)); // implement // base 16 here, // example, 15x15 // board } } public board(board b) { // duplicates board, keeps references // queens conserve memory, 96 total queens // in existence through search! (queen q : b.queens) { queens.add(q); } } public boolean checkforimpact() { (int = 0; < queens.size(); i++) { (int j = + 1; j < queens.size(); j++) { if (queens.get(i).checkknight(queens.get(j))) { // check // // queens // intersecting, // 1 hit // enough return true; } } } return false; } public arraylist<board> getchildboards() { // create child boards // single queen removed arraylist<board> boards = new arraylist<board>(); (int = 0; < queens.size(); i++) { boards.add(new board(this)); } int = 0; (board b : boards) { b.queens.remove(i); i++; } return boards; } public string drawboard() { string s = ""; char[][] printableboard = new char[boardsize][boardsize]; (int = 0; < 8; i++) { (int j = 0; j < 8; j++) { printableboard[i][j] = '_'; } } (queen q : queens) { printableboard[q.i][q.j] = 'q'; } s += " b c d e f g h\n"; (int = 0; < 8; i++) { s += (8 - i) + "|"; (int j = 0; j < boardsize; j++) { s += printableboard[i][j]; s += "|"; } s += "\n"; } return s; } } test class
import java.util.arraylist; public class test { static string[] boards = { "24683175", "17468253", "17582463", "41582736", "51842736", "31758246", "51468273", "71386425", "51863724", "57142863", "63184275", "53172864" }; // 12 solutions 8 // queens problem static arraylist<board> boardobjects = new arraylist<board>(); public static void main(string[] args) { (string queens : boards) { // create starter boards boardobjects.add(new board(queens)); } int i; arraylist<board> foundboards = null; (i = 8; > 0; i--) { arraylist<board> newboards = new arraylist<board>(); foundboards = new arraylist<board>(); (board b : boardobjects) { if (b.checkforimpact()) { // if queen intercepts // children arraylist<board> boardstobeadded = b.getchildboards(); // pass // // permutations // of // queens // once // removed (board bo : boardstobeadded) { newboards.add(bo); // add in next list } } else { foundboards.add(b); // if have no impact, have // 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>(); (board board : foundboards) { string createdboard = board.drawboard(); boolean found = false; (string storedboard : winningcombinations) { if (storedboard.equals(createdboard)) found = true; } if (!found) winningcombinations.add(createdboard); } (string board : winningcombinations) { system.out.println(board); } } } the end output is:
the maximum number of super-queens is: 6 b c d e f g h 8|q|_|_|_|_|_|_|_| 7|_|_|_|_|_|_|q|_| 6|_|_|_|q|_|_|_|_| 5|_|_|_|_|_|_|_|_| 4|_|_|_|_|_|_|_|q| 3|_|q|_|_|_|_|_|_| 2|_|_|_|_|q|_|_|_| 1|_|_|_|_|_|_|_|_| b c d e f g h 8|q|_|_|_|_|_|_|_| 7|_|_|_|_|_|_|_|_| 6|_|_|_|_|q|_|_|_| 5|_|_|_|_|_|_|_|q| 4|_|q|_|_|_|_|_|_| 3|_|_|_|_|_|_|_|_| 2|_|_|_|_|_|q|_|_| 1|_|_|q|_|_|_|_|_| b c d e f g h 8|_|_|_|_|q|_|_|_| 7|q|_|_|_|_|_|_|_| 6|_|_|_|_|_|_|_|q| 5|_|_|_|q|_|_|_|_| 4|_|_|_|_|_|_|_|_| 3|_|_|_|_|_|_|_|_| 2|_|_|q|_|_|_|_|_| 1|_|_|_|_|_|q|_|_| b c d e f g h 8|_|_|_|_|q|_|_|_| 7|q|_|_|_|_|_|_|_| 6|_|_|_|_|_|_|_|q| 5|_|_|_|q|_|_|_|_| 4|_|_|_|_|_|_|_|_| 3|_|_|_|_|_|_|q|_| 2|_|_|q|_|_|_|_|_| 1|_|_|_|_|_|_|_|_| b c d e f g h 8|_|_|_|_|q|_|_|_| 7|q|_|_|_|_|_|_|_| 6|_|_|_|_|_|_|_|q| 5|_|_|_|_|_|_|_|_| 4|_|_|q|_|_|_|_|_| 3|_|_|_|_|_|_|q|_| 2|_|_|_|_|_|_|_|_| 1|_|_|_|q|_|_|_|_| i've removed duplicates , made nice board printing method. don't remember exact math, highlights 40 possible locations. there others, looking, we've found fair chunk of them already! here, can gently shift individual queens around. cursory look, each board has single piece can moved 3 additional spaces, know there 160 solutions.
conclusions
with application, run-time on machine less second, meaning if attached standard queens application, additional knight's brute-forcing have no impact on process , have same run-time. in addition, because 6-piece puzzles possible, know eventual application run finish finding @ 6th piece being placed, no more solutions possible, since there no viable 7-piece , 8-piece solutions.
in other words, finding maximum super-queen layout shorter maximum queen layout due additional restrictions!
Comments
Post a Comment