Reputation: 27
8 Queens need to restart for full board without 8 queens
So i have written a code that will continue to place queens on a chess board until there are no more possible board spaces where a queen can sit with out being taken by another queen. The problem is my chess board should have 8 queens when it finishes however my board on has 5 (my board also no longer has any spaces on which i can place a queen) I am wondering how (using as much of my current code as possible) is there any way to allow my algorithm to restart when i reach a point where i do not yet have 8 queens on the board but have covered all possible positions?
here is my code / output:
public class Driver {
public static void main(String[] args) {
Driver run = new Driver();
run.it();
}
public void it() {
Tester test = new Tester();
test.fillBoard();
test.placeQueens();
test.printBoard();
}
}
public class Tester {
public char [][] board = new char [8][8];
public void fillBoard() {
for(int i = 0; i < 8; i++) {
for(int j = 0; j < 8; j++) {
board[i][j] =' ';
}
}
}
public boolean checkUp(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkUp(row - 1, col);
}
}
}
public boolean checkDown(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkDown(row + 1, col);
}
}
}
public boolean checkUpAndRight(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkUpAndRight(row - 1, col - 1);
}
}
}
public boolean checkDownAndRight(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkDownAndRight(row + 1, col - 1);
}
}
}
public boolean checkUpAndLeft(int row, int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkUpAndLeft(row - 1, col + 1);
}
}
}
public boolean checkDownAndLeft(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkDownAndLeft(row + 1, col + 1);
}
}
}
public boolean checkLeft(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkLeft(row, col + 1);
}
}
}
public boolean checkRight(int row , int col) {
if (((row < 0) || (row > 7)) || ((col > 7) || (col < 0))) {
return true;
} else {
if (board[row][col] == 'Q') {
return false;
} else {
return checkRight(row, col - 1);
}
}
}
public boolean checkSpot(int row, int col) {
if ((checkUp(row, col) == true) && (checkDown(row, col) == true) &&
(checkUpAndRight(row, col) == true) && (checkDownAndRight(row, col) == true) &&
(checkUpAndLeft(row, col) == true) && (checkDownAndLeft(row, col) == true) &&
(checkLeft(row, col) == true) && (checkRight(row, col) == true)) {
return true;
} else {
return false;
}
}
public void placeQueens() {
for(int col = 0; col < 8; col++) {
for(int row = 0; row < 8; row++) {
if(checkSpot(row, col) == true) {
board[row][col] = 'Q';
}
}
}
}
public void printBoard() {
String rtn = "";
String newRow = "+---+---+---+---+---+---+---+---+\n";
rtn += newRow;
rtn += "| "+ board[0][0] +" | "+ board[0][1] +" | "+ board[0][2] +" | "+ board[0][3] +" | "
+ board[0][4] +" | "+ board[0][5] +" | "+ board[0][6] +" | "+ board[0][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[1][0] +" | "+ board[1][1] +" | "+ board[1][2] +" | "+ board[1][3] +" | "
+ board[1][4] +" | "+ board[1][5] +" | "+ board[1][6] +" | "+ board[1][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[2][0] +" | "+ board[2][1] +" | "+ board[2][2] +" | "+ board[2][3] +" | "
+ board[2][4] +" | "+ board[2][5] +" | "+ board[2][6] +" | "+ board[2][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[3][0] +" | "+ board[3][1] +" | "+ board[3][2] +" | "+ board[3][3] +" | "
+ board[3][4] +" | "+ board[3][5] +" | "+ board[3][6] +" | "+ board[3][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[4][0] +" | "+ board[4][1] +" | "+ board[4][2] +" | "+ board[4][3] +" | "
+ board[4][4] +" | "+ board[4][5] +" | "+ board[4][6] +" | "+ board[4][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[5][0] +" | "+ board[5][1] +" | "+ board[5][2] +" | "+ board[5][3] +" | "
+ board[5][4] +" | "+ board[5][5] +" | "+ board[5][6] +" | "+ board[5][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[6][0] +" | "+ board[6][1] +" | "+ board[6][2] +" | "+ board[6][3] +" | "
+ board[6][4] +" | "+ board[6][5] +" | "+ board[6][6] +" | "+ board[6][7] +" |\n";
rtn += newRow;
rtn += "| "+ board[7][0] +" | "+ board[7][1] +" | "+ board[7][2] +" | "+ board[7][3] +" | "
+ board[7][4] +" | "+ board[7][5] +" | "+ board[7][6] +" | "+ board[7][7] +" |\n";
rtn += newRow;
System.out.print(rtn);
}
}
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | Q | | | | |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | Q | | | |
+---+---+---+---+---+---+---+---+
| | | Q | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
Upvotes: 0
Views: 189
Answers (2)
Reputation: 12239
If you place a queen and it turns out that you can't complete the board, you should remove the queen. Then you should move on to the next cell and try to place the queen again.
Ah, but how do you go about placing the next queen? How can you start another pair of nested loops to go along the board and try each cell? The answer is recursion, which is a fancy way of saying that your function calls itself.
The first time you call your function, it looks for an available cell. After placing a queen, it calls itself to place a second queen. The second copy of the function, once it has placed a queen, calls itself to place a third queen.
When does the recursion stop? When the last queen has been placed. The function can keep track of the number of queens remaining with a parameter that it decrements when it calls itself. Initially the parameter has the value 8. On each recursive call, its value drops by 1. When it reaches 0, all queens have been placed and the function can return without doing any further work.
Take a look at this:
import java.lang.*;
import java.util.*;
import java.io.*;
public class EightQueens {
char board[][] = new char[8][8];
// Eight directions of attack:
int dr[] = { -1, -1, -1, 0, 1, 1, 1, 0 },
dc[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
public void clearBoard() {
for (int r = 0; r < 8; ++r) {
for (int c = 0; c < 8; ++c) {
board[r][c] = ' ';
}
}
}
public void printBoard() {
String separator = "+---+---+---+---+---+---+---+---+\n";
StringBuffer buf = new StringBuffer();
buf.append(separator);
for (int r = 0; r < 8; ++r) {
for (int c = 0; c < 8; ++c) {
buf.append("| "+board[r][c]+" ");
}
buf.append("|\n"+separator);
}
System.out.println(buf.toString());
}
boolean available(int r, int c) { // Returns true if no queen is
for (int i = 0; i < 8; ++i) { // attacking this cell.
int R = r, C = c;
while (R >= 0 && R < 8 && C >= 0 && C < 8) {
if (board[R][C] != ' ') {
return false;
}
R += dr[i]; // Use the directional arrays
C += dc[i]; // to go along the eight
} // lanes of attack.
}
return true;
}
boolean placeQueen(int count) { // Returns true only on success.
if (count == 0) {
return true; // All queens have been placed.
}
for (int r = 0; r < 8; ++r) {
for (int c = 0; c < 8; ++c) {
if (available(r, c)) {
board[r][c] = 'Q'; // Tentatively place a queen.
if (placeQueen(count-1)) { // Notice the decremented count.
return true; // If it worked, we're done.
}
board[r][c] = ' '; // If not, remove the queen.
}
}
}
return false;
}
public static void main(String[] args) {
EightQueens test = new EightQueens();
test.clearBoard();
test.placeQueen(8);
test.printBoard();
}
}
My code is much shorter than yours because I looked for places to cut down on repetition. Compare my printBoard to yours. And look at how I implemented the cell check. One function is enough.
What will interest you most of all is the recursive function placeQueen. Study it and adapt the idea to your own code.
I see that your current cell-checking functions make use of recursion, so you seem to be familiar with the general idea. It's just that you used it in the wrong place. You can use nested loops to check the lanes of attack, and apply the concept of recursion in the queen-placing function.
Upvotes: 1
Reputation: 5
Here is a nice link to get started in algorithm trees and recursive backtracking https://www.cs.utexas.edu/~scottm/cs307/handouts/recursiveBacktrackingExplanation.htm
Basically you don't need to restart but "search" for every possible solutions, in an ordered way, so you know the board positions you have already tried and you don't try that again.
Upvotes: 0
Related Questions
- Eight Queens - Diagonal Movement
- How can I skip duplicate board states in N-Queen problem?
- Java: How to implement N-Queens?
- 8 queens problem
- Not able to find possible solutions for N-Queens puzzle
- What's wrong with my solution of N-Queens?
- 8 queens problem using backtracking recurison
- 5 queens on a 8x8 chess board
- 8 Queens Algorithm: Not getting full result set
- Optimizing N queens puzzle