8 Algorithm without attack on hens with recursion

Question

I am having a problem with the encoding problem of 8 queens. I coded a class to help me solve it, but for some reason I am doing something wrong. I understand what is going to happen.

In addition, we must use recursion to solve it, but I don’t know how to use the backtracking that I read about, so I just used it in methods that check if the position is legitimate.

My board String [] [] board = { { "O", "O"... etc. etc. with 8 rows and 8 columns. If I get something wrong conceptually or make a serious Java error, say this: D Thank you!

 public void solve () { int Queens = NUM_Queens - 1; while (Queens > 0) { for (int col = 0; col < 8; col++) { int row = -1; boolean c = false; while (c = false && row < 8) { row ++; c = checkPos (row, col); } if (c == true) { board[row][col] = "Q"; Queens--; } else System.out.println("Error"); } } printBoard (); } // printing the board public void printBoard () { String ret = ""; for (int i = 0; i < 8; i++) { for (int a = 0; a < 8; a++) ret += (board[i][a] + ", "); ret += ("\n"); } System.out.print (ret); } // checking if a position is a legitimate location to put a Queen public boolean checkPos (int y, int x) { boolean r = true, d = true, u = true, co = true; r = checkPosR (y, 0); co = checkPosC (0, x); int col = x; int row = y; while (row != 0 && col != 0 ) { //setting up to check diagonally downwards row--; col--; } d = checkPosDD (row, col); col = x; row = y; while (row != 7 && col != 0 ) { //setting up to check diagonally upwards row++; col--; } d = checkPosDU (row, col); if (r = true && d = true && u = true && co = true) return true; else return false; } // checking the row public boolean checkPosR (int y, int x) { if (board[y][x].contentEquals("Q")) return false; else if (board[y][x].contentEquals("O") && x == 7) return true; else //if (board[y][x].contentEquals("O")) return checkPosR (y, x+1); } // checking the column public boolean checkPosC (int y, int x) { if (board[y][x].contentEquals("Q")) return false; else if (board[y][x].contentEquals("O") && y == 7) return true; else //if (board[y][x].contentEquals("O")) return checkPosR (y+1, x); } // checking the diagonals from top left to bottom right public boolean checkPosDD (int y, int x) { if (board[y][x].contentEquals("Q")) return false; else if (board[y][x].contentEquals("O") && (x == 7 || y == 7)) return true; else //if (board[y][x].contentEquals("O")) return checkPosR (y+1, x+1); } // checking the diagonals from bottom left to up right public boolean checkPosDU (int y, int x) { if (board[y][x].contentEquals("Q")) return false; else if (board[y][x].contentEquals("O") && (x == 7 || y == 0)) return true; else //if (board[y][x].contentEquals("O")) return checkPosR (y-1, x+1); } } 

Answer 1

Like this homework, solution, but not in code.

Try writing a method that only handles what should happen in a single column; here you have to use recursion. Try again, checking if there is a solution, if not, undo the last change (i.e., change the position of the queen) and try again. If you focus on only one part of the problem (one column), this is much easier than thinking about all the columns at once.

And as Quetzalcoatl points out, you assign false your variable in the first loop. You probably don't want to do this. You should always include all warnings in your compiler (run javac with -Xlint) and fix them.

Answer 2

You are trying to use some brute force, but, as you mentioned, you have no recursion. Your programs put the queen in first place. But in the end, no solution was found. It follows that your first guess (the position of your first queen) is not valid. You must return to this state. And you need to assume that your checkPos (x, y) is false instead of true.

Now some tips:

• As mentioned above, NPE int[N] queens is a more suitable representation.
• sum (queens) must be 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28, as the position must be unique.
• Instead of checking only the position of the new queen, you can check the whole situation. Indeed, if for all (i, j) \ in N ^ 2 with queen (i) = j there does not exist (k, l)! = (I, j) with abs (ki) == abs (lj)