Ошибки логики N-Queens Backtracking / Recursion?

Я пытаюсь решить эту проблему в качестве практического упражнения для моего предстоящего теста. Это требует, чтобы я запрограммировал программу на C ++, которая запрашивает ввод «размера платы» (nxn) и «числа ферзей», а затем выполняет задачу «n-куинс».

Эта проблема с n-ферзями отличается от «нормальной» проблемы с n-ферзями тем, что число ферзей и размер доски могут варьироваться, а если доска заполнена не полностью, заменяются открытые пространства.

Пример вывода для ввода размера ‘8’ и номера ферзя ‘4’ можно увидеть ниже:

O.......
..O.....
....O...
.O......
...­-..­.-
........
...­-.-..
...­-.­.-.

где ‘O’ представляет пространство, которое занимает королева, ‘.’ представляет пространство, которое заблокировано другой королевой, а ‘-‘ представляет пространство, которое мог быть занятым другой королевой, если пользователь ввел большее количество ферзей (то есть открытое пространство).

Дело в том, что я закодировал проблему, и это дает мне КРАЙНЕ противоречивые результаты. (пример: ввод 4,4 работ, 5,5 работ, 6,6 не работа, 7,7 работы, 8,8 не работа, 2,1 не работа …. список можно продолжать и продолжать). Я обнаружил, что виновником является комбинация цикла for и рекурсии, возвращающейся обратно в стек после того, как это сделано, вызывая несколько ошибок в зависимости от ситуации. Мой вопрос заключается в том, как мне исправить рекурсивный цикл, чтобы он по-прежнему мог возвращаться назад, не вызывая при этом ненужных ошибок? Я новичок в идее «возврата» в сочетании с рекурсией; что я могу сделать, чтобы улучшить мой метод возврата в будущем?

Мой код выглядит следующим образом:

#include <iostream>
#include <cstdlib>
using namespace std;

void readBoard(char board[100][100], int size);
void printBoard(char board[100][100], int size);
bool findOpenSpot(char board[100][100], int row, int col, int size);
bool nQueenSolver(char board[100][100], int row, int size, int queenNumber);

int main()
{
int queenNumber;
int size;
char b[100][100];
cout << "What size board do you want?" << endl;
cin >> size;
readBoard(b, size);
printBoard(b, size);
cout << "How many queens do you want to place?" << endl;
cin >> queenNumber;
if (queenNumber > size)
{
cout << "Impossible." << endl;
exit(0);
}
if (nQueenSolver(b, 0, size, queenNumber) == true)
{
printBoard(b, size);
}
else
{
cout << "Impossible." << endl;
}
return 0;

}
bool nQueenSolver(char board[100][100], int row, int size, int queenNumber)
{
if (row >= size)
{
return true;
}

for (int j=0; j<size; j++)
{
if (findOpenSpot(board, row, j, size) == true)
{
if (queenNumber >= 0)
{
board[row][j] = 'Q';
cout << "Subtracting one queen." << endl;
}
else if (queenNumber < 0)
{
board[row][j] = '-'; //If all queens have already been placed, start showing open slots.
}
if (nQueenSolver(board, row+1, size, queenNumber) == true) //Recursion to cycle down the rows
{
return true;
}
board[row][j] = '.'; //Backtracking if needed.
}

}
return false;
}

bool findOpenSpot(char board[100][100], int row, int col, int size)
{
int i, j;
for (i=0; i<col; i++)
{
if (board[row][i] == 'Q') //Checks if there's any queens to the left of the index
{
return false; //Not an open spot.
}
}
i = row; j = col;
while (i >= 0 && j >= 0)
{
if (board[i][j] == 'Q') //Checks if there's any queens in the upper left diagonal of the index
{
return false;
}
i--; j--;
}

for (i=0; i<row; i++)
{
if (board[i][col] == 'Q') //Checks if there's any queens on top of the index
{
return false;
}
}

i = row; j = col;
while (i >= 0 && j >= 0)
{
if (board[i][j] == 'Q') //Checks if there's any queens in the upper right diagonal of the index
{
return false;
}
i--; j++;
}

return true; //This index isn't threatened by a queen, go ahead and place one here!
//Open spot!!
}void readBoard(char board[100][100], int size)
{
for (int i=0; i<size; i++) //Puts in the size of the board into the array.
{
for (int j=0; j<size; j++)
{
board[i][j] = '.';
}
}
}

void printBoard(char board[100][100], int size)
{
for (int i=0; i<size; i++) //Prints the 'board' part of the array. (Doesn't print the entire array)
{
for (int j=0; j<size; j++)
{
cout << board[i][j];
}
cout << endl;
}
}

Я также пытался искать помощь в Интернете и не нашел ее (как в stackoverflow, так и в Google. Только фрагменты информации, которые я уже использовал). Любая помощь будет принята с благодарностью! 🙂