Восемь королей, использующих backtracking and recursion C++

Question

Я только что научился возвращаться назад и рекурсии и имею назначение для использования в проблеме восьми королей. Я должен пригласить пользователя ввести строку, а затем процедура place_next_queen (bool &) должна попытаться разместить следующую королеву в следующем столбце. Эта процедура является рекурсивной функцией, и я считаю, что в этом проблема. Пожалуйста, посмотрите, любая помощь будет принята с благодарностью! И, пожалуйста, дайте мне знать, если вам нужна дополнительная информация ... Проблема в том, что программа правильно печатает 1 в первом столбце, а остальная часть платы - все нули.

Вот мой класс EightQueensProblem:

class EightQueensProblem 
{ 
public: 
//Default constructor, initializes NUM_QUEENS to 8 in initializer list 
EightQueensProblem() : NUM_QUEENS(8){}; 
void clear_board(); 
void display_board(ostream& os); 
bool queen_under_attack(int row, int column); 
bool start_game(int row); 
private: 
static const int CHESSBOARD_SIZE = 8; 
//2D array of int values not on the heap of dimension CHESSBOARD_SIZE x CHESSBOARD_SIZE 
int chessboard[CHESSBOARD_SIZE][CHESSBOARD_SIZE]; 
const int NUM_QUEENS; 
//int representing number of queens currently placed on the chessboard 
int num_queens_on_board; 
void place_queen_on_square(int row, int column); 
void remove_queen_from_square(int row, int column); 
void place_next_queen(bool& done); 
}; 

void EightQueensProblem::clear_board() 
{ 
//resets all squares on chessboard to value 0 
for(int row = 0; row < CHESSBOARD_SIZE; row ++) 
{ 
    for(int column = 0; column < CHESSBOARD_SIZE; column ++) 
    { 
     chessboard[row][column] = 0; 
    } 
} 
//sets number of queens on board to 0 
num_queens_on_board = 0; 
} 

void EightQueensProblem::display_board(ostream& os) 
{ 
//outputs chessboard to given output stream without changing calling object 
for(int row = 0; row < CHESSBOARD_SIZE; row ++) 
{ 
    for(int column = 0; column < CHESSBOARD_SIZE; column++) 
    { 
     os << chessboard[row][column] << " "; 
    } 
    os << endl; 
} 
} 

bool EightQueensProblem::queen_under_attack(int row, int column) 
{ 
//detect if a queen occupies a square along the southwest diagonal of square (row, col) 
for(int i = 0; (row + i) < CHESSBOARD_SIZE && (column - i) >= 0; i ++) 
{ 
    if(chessboard[row + 1][column - i] != 0) 
     return true; 
} 
//along southeast diagonal 
for(int i = 0; (row + i) < CHESSBOARD_SIZE && (column + i) < CHESSBOARD_SIZE; i ++) 
{ 
    if(chessboard[row + i][column + i] != 0) 
     return true; 
} 
//along northwest diagonal 
for(int i = 0; (row - i) >= 0 && (column - i) >= 0; i ++) 
{ 
    if(chessboard[row - i][column - i] != 0) 
     return true; 
} 
//along northeast diagonal 
for(int i = 0; (row - i) >= 0 && (column + i) < CHESSBOARD_SIZE; i ++) 
{ 
    if(chessboard[row - i][column + i] != 0) 
     return true; 
} 
//along same row 
for(int i = 0; i < CHESSBOARD_SIZE; i ++) 
{ 
    if(chessboard[row][i] != 0) 
     return true; 
} 
//along same column 
for(int i = 0; i < CHESSBOARD_SIZE; i ++) 
{ 
    if(chessboard[i][column] != 0) 
     return true; 
} 
return false; 
} 

bool EightQueensProblem::start_game(int row) 
{ 
//places the first queen at the given row in the left most column 
chessboard[row][0] = 1; 
    num_queens_on_board = 1; 
bool done; 
place_next_queen(done); 
if(done == true) 
    return true; 
else 
    return false; 
} 

void EightQueensProblem::place_queen_on_square(int row, int column) 
{ 
//places a queen on the board at the given location (row, column) 
chessboard[row][column] = column + 1; 
    num_queens_on_board++; 
} 

void EightQueensProblem::remove_queen_from_square(int row, int column) 
{ 
//removes a queen from the board at the given location (row, column) 
chessboard[row][column] = 0; 
    num_queens_on_board--; 
} 

void EightQueensProblem::place_next_queen(bool& done) 
{ 
if(num_queens_on_board == NUM_QUEENS) 
{ 
    done = true; 
} 
else 
{ 
    done = false; 
    for(int row = 0; row < (num_queens_on_board - 1); row ++) 
{ 
    if(!queen_under_attack(row, num_queens_on_board)) 
    { 
     place_queen_on_square(row, num_queens_on_board); 
     place_next_queen(done); 
    } 
    else 
    { 
     remove_queen_from_square(row, num_queens_on_board); 
     row ++; 
     place_queen_on_square(row, num_queens_on_board); 
     place_next_queen(done); 
    } 
} 
    } 
    } 

Вот моя главная функция:

int main() 
{ 
cout << "Position the first queen on the chessboard:" << endl << endl; 
cout << "Enter the row for the first queen (from 1 to 8): "; 
int input_row; 
cin >> input_row; 
cout << "From the position (" << input_row << ", 1), the EightQueensProblem has solution: " << endl << endl; 

EightQueensProblem game; 
game.clear_board(); 
game.start_game(input_row); 
game.display_board(cout); 
string TargetFileName = "Solutions.txt"; 
ofstream out(TargetFileName); 
game.display_board(out); 
out.close(); 

return 0; 
} 

Answer 1

Это не решение, но это слишком долго для комментария. Я отредактирую его после того, как будут рассмотрены проблемы.

Как это работает вообще, это вне меня. Я скопирован код, сохраните главную функцию, а именно:

int main() { 
    EightQueensProblem e; 

    e.clear_board(); 
    e.start_game(1); 
    e.display_board(cout); 
} 

1. Игра запускается не поставив ферзя на доске
2. Зов место следующая королева
3. num_queens_on_board, никогда не будучи измененное, по-прежнему 0
4. queen_under_attack возвращает истину (всегда)
5. ранее размещенных матка удалена (почему?)
6. Новый один palced
7. Повторить 2-7

В небольшой доле иронии, так как рекурсия следует тем же шагам, он никогда не останавливается, и я получаю StackOverflow. Я думаю, вам нужно пройти через вашу логику (облегчить работу с отладчиком) и исправить, где вы ошибетесь.