How can I modify this recursive backtracking algorithm (NQueens) to find all solutions instead of just one?

Question

I have written a method that uses recursion and backtracking to find one solution to the N-Queens problem. What I want to do now is modify this method so that it can find all possible solutions. I assume that I need to use a 2D integer array for storing all of the solutions, and also add a counter that increments each time a solution is found. But I just can't seem to wrap my head around how I can make this method continue once I find a solution and continue backtracking to find all of the other possible solutions. I think what I have to do is get rid of the "return true;" that occurs when a solution is found, but then I have no idea how to make the method recursively determine if a solution is found.... Here's the one-solution version I have right now:

public boolean placeQueens(int x, int y) {
    if (!underAttack(x, y)) {
        queen[x] = y;
        board[x][y] = true;
        if (x + 1 == boardSize
                ||placeQueens(x + 1, 0)) {
            return true;
        }
        queen[x] = 0;
        board[x][y] = false;
    }
    if (y + 1 == boardSize) {
        return false;
    }
    return placeQueens(x, y + 1);
}

Edit: Fixed the method, the result is below. It's still possibly kind of messy, but it works! Instead of printing each solution as it is found, I added it to an array. The reason I still have the queen[] variable is so that I can have the solution array be independent from the board state. And the reason I still have the board[][] variable is because it makes the underAttack() method much easier to write (particularly with calculating slopes).... Anyway, I really appreciate the help everyone!

public void placeQueen(int x) {
    if (x == N) {            
        for (int i : queen) {
            solution[counter][i] = queen[i];
        }
        counter++;            
        return;
    }
    for (int y = 0; y < N; y++) {
        if (!underAttack(x, y)) {                
            queen[x] = y;
            board[x][y] = true;
            placeQueen(x + 1);
            queen[x] = 0;
            board[x][y] = false;
        }
    }
}

Answer 1

Currently you are just looking for one solution. When you find a x,y where you can place a queen you move a column forward and try to place the queen in the following column.

For generating all the solutions, rather than returning true, you can print the final array at the end, backtrack and change your position at the current column and try generating the solutions again.

The pseudocode can be something like this

Place(x)

  // Here x is the column number where you want to put the queen
  if (x == board_size + 1):
      print (array A)
      return;
  for y from 0 to board_size:
       if (!underattack(A,x,y)) // A[x] = y => the queen is at row y in col x
            A[x] = y
            Place(x+1)
  return;

Here even if we find a particular (x,y) that works, we backtrack and try subsequent values of y for the current x.

Answer 2

Here is a pseudo code for NQueens:-

void Nqueens(int row,int columns[],int n) {

if(row<n) {

for(int col=0;col<n;col++) {

  if(safe(row,col,columns)) {

     columns[i] = k;
     NQueens(row+1,columns);
  }

}



}

else {

   printf("solution: \n");

   for(int i =0;i<n;i++) {

       printf("(%d,%d)\n",i,columns[i]);
   }

}

}