For a project I had to write a program that recursively solves the 8 Queens Puzzle in all 92 solutions. The program works fine until you make the "main" method run recursively. The odd part is that it throws the error at a point that is not related to the "main" method's loop (including in the toString method). I have tried to place the recursive call everywhere possible and even my instructor can't figure it out. I also have to mention that moving the recursive call for the loop moves where it throughs the error and the program is inconsistent with at what solution throws the error.
import java.util.Scanner;
public class NonAttackingQueens {
private Scanner scan = new Scanner(System.in);
//Row
private int r = 0;
//Column
private int c = 0;
private int solution = 1;
private int[] taken = {9,9,9,9,9,9,9,9};
private int[][] board = {
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}};
public static void main(String[] args){
NonAttackingQueens board = new NonAttackingQueens();
}
public NonAttackingQueens(){
place();
}
//This is the main method that runs everything.
private void place(){
//There are only 92 solutions, and this stops it after the 92th iteration
while (solution <= 92){
//If r==8 then it has found a solution
if (r == 8){
System.out.println(this);
r = 7;
//This forces the program to continue
//It removes the last queen tries to move it right one
backTrack(0);
//The Scanner is used to pause the program after every solution
//Just hit enter to continue
scan.nextLine();
//place();
}
else {
//If it is not a legal spot
if (poss()){
board[r][c] = 1;
//The taken array is the location of all the queens
//It works the same as a regular coordinate system
//but being an array is a little more difficult to read
/*
* 0 1 2 3 4 5 6 7
* 0 9 9 9 9 9 3 9 9
* 1 9 9 9 9 9 3 9 9
* 2 9 9 9 9 9 3 9 9
* 3 9 9 9 9 9 3 9 9
* 4 9 9 9 9 9 3 9 9
* 5 9 9 9 9 9 3 9 9
* 6 9 9 9 9 9 3 9 9
* 7 9 9 9 9 9 3 9 9
*
* {9,9,9,9,9,3,9,9}
*
*/
//The element of the array is equal to its column
//The value of the element is equal to its row
//So a queen in row 3 column 5 is equal
//is equal to taken[5]=3;
//Or the entire first solution would have to array equal
//{0,6,4,7,1,3,2,5}
taken[c] = r;
r++;
c = 0;
//place();
}
//Then find a new one
else {
findNext();
//This is how it would run recursively........
//If it did not give a stack overflow
//this.place();
}
}
place();
}
}
//Tests if it is legal to move here
private boolean poss(){
if (c >= 8 || taken[c] != 9 || diag()) return false;
else return true;
}
//Checks for any diagonal attacks
//It's logic is opposite of the other two conditions in the .poss()
private boolean diag(){
int left = c;
int right = c;
int tmpR = r;
boolean found = false;
while (left >= 0 && tmpR >= 0){
if (board[tmpR][left] == 1) {
found = true;
}
tmpR -= 1;
left -= 1;
}
tmpR = r;
//These worked intuitively
//They go up one row then left or right one column
//If it hits a 1 then there's a diagonal
//If it hits -1 then there is not
while (right <= 7 && tmpR >= 0 && found != true){
if (board[tmpR][right] == 1){
found = true;
}
tmpR -= 1;
right += 1;
}
return found;
}
//This literally keeps going right until it finds an opening or hits the right side
//Then it does the back track method
private void findNext(){
//The last column did not work so it immediately goes to the next one
c++;
//100% recursive
if (c < 8){
//Tests if it is a legal spot
if (poss()){
return;
}
//If not then go to the next column
else findNext();
}
//If it hits the right side then it back tracks
else {
//Nothing on this row so immediately go to the one before
r--;
backTrack(0);
}
}
private void backTrack(int x){
if (x < taken.length){
//This is the main reason why I have the taken array
//It checks every array element until it finds the one equal to the
//element that needs to be removed.
//It changes that element to 9 and removes it from the board
//It then makes c equal one more than the column it just removed the element from
if (taken[x] == r){
taken[x] = 9;
board[r][x] = 0;
c = x + 1;
return;
}
else {
x++;
backTrack(x);
}
}
}
public String toString(){
String result="Solution: "+solution+"\n";
for (int i=0; i<board.length; i++){
for (int j=0; j<board[i].length; j++){
result += board[i][j];
}
result += "\n";
}
solution++;
return result;
}
}
To make it run recursive change the while in the place method to if and uncomment the .place() methods.
