Как я могу изменить этот рекурсивный алгоритм обратного отслеживания (NQueens), чтобы найти все решения вместо одного?

Question

Я написал метод, который использует рекурсию и возврат, чтобы найти одно решение проблемы N-Queens. Теперь я хочу изменить этот метод, чтобы он мог найти все возможные решения. Я предполагаю, что мне нужно использовать двумерный целочисленный массив для хранения всех решений, а также добавить счетчик, который увеличивается каждый раз, когда решение найдено. Но я просто не могу понять, как заставить этот метод продолжать, как только я найду решение и продолжу возвращаться, чтобы найти все другие возможные решения. Я думаю, что я должен сделать, это избавиться от "верни истину"; это происходит, когда решение найдено, но тогда я понятия не имею, как заставить метод рекурсивно определить, найдено ли решение.... Вот версия с одним решением, которую я имею прямо сейчас:

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);
}

Редактировать: Исправлен метод, результат ниже. Это все еще возможно немного грязно, но это работает! Вместо того, чтобы печатать каждое решение в том виде, в котором оно найдено, я добавил его в массив. Причина, по которой у меня по-прежнему есть переменная queen[], заключается в том, что массив решений может быть независимым от состояния платы. И причина, по которой у меня все еще есть переменная board[][], заключается в том, что она значительно облегчает написание метода underAttack() (особенно при расчете уклонов).... В любом случае, я действительно ценю помощь всех!

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

В настоящее время вы просто ищете одно решение. Когда вы найдете топор, y, где вы можете поместить королеву, вы перемещаете столбец вперед и пытаетесь поместить королеву в следующий столбец.

Для генерации всех решений, вместо того, чтобы возвращать true, вы можете напечатать окончательный массив в конце, вернуться назад и изменить свою позицию в текущем столбце и попытаться сгенерировать решения снова.

Псевдокод может быть примерно таким

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;

Здесь, даже если мы находим конкретный (x,y), который работает, мы возвращаемся назад и пробуем последующие значения y для текущего x.

Answer 2

Вот псевдокод для 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]);
   }

}

}