I'm in the process of writing a knights tour algorithm for a homework. I believe my algorithm is a good one and don't see anything wrong with it, but for some reason my program keeps throwing a stack overflow error. I don't see any reason why it would be throwing such an error, so maybe you guys could pick up on something I don't see. Most of the variables have been defined in a header file.
Here is a run down of the program.
First the constructor is called and knight_square gets initialized with 0's except the start position which gets set to 1, then count gets incremented.
Next solve_from is called and checks if the board is solved with is_solved. If not, it goes into a for loop, which checks to see if from the current position any of the 8 possible moves are valid. If so, insert the value and recursively call solve_from again. If no valid moves are possible, then that position gets removed and the current row and column get reverted back to the previous value.
If anyone catches any errors below or gets the program to work for them I'd appreciate any feedback.
Thanks.
#include <iostream>
#include "knight.h"
const int moves = 8;
const int x_inc [moves] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int y_inc [moves] = {1, -1, 2, -2, -2, 2, -1, 1};
using namespace std;
//Initializes count which keeps track of the moves, current row and current column.
knight::knight(int size, int start_row, int start_col)
{
count = 1;
board_size = size;
curr_row = start_row;
curr_col = start_col;
for (int row = 0; row < board_size; row++)
{
for (int col = 0; col < board_size; col++)
{
if ((start_row == row) && (start_col == col))
knight_square[row][col] = count;
else
knight_square[row][col] = 0;
}
}
count++;
}
//Attempts to solve the board by adding knights in valid positions
void knight::solve_from(knight &tour)
{
if (tour.is_solved())
{
cout << "Solved!" << endl;
tour.print();
return;
}
else
{
for (int i = 0; i < 8; i++)
{
if (tour.move((curr_row + x_inc[i]), (curr_col + y_inc[i])))
{
tour.insert((curr_row + x_inc[i]), (curr_col + y_inc[i]));
}
tour.solve_from(tour);
}
}
tour.remove(curr_row, curr_col);
}
//Checks to see if a move is valid.
bool knight::move(int row, int col)
{
if (row < 0 || row >= board_size)
return false;
else if (col < 0 || col >= board_size)
return false;
else if (knight_square[row][col] != 0)
return false;
else
return true;
}
//Inserts a knight into position if move is valid then increments the count.
void knight::insert(int row, int col)
{
cout << "Insert : " << count << endl;
knight_square[row][col] = count;
curr_row = row;
curr_col = col;
count++;
}
//Removes knight
void knight::remove(int row, int col)
{
count--;
cout << "Remove : " << count << endl;
for (int rows = 0; rows < board_size; rows++)
{
for (int cols = 0; cols < board_size; cols++)
{
if (knight_square[rows][cols] == (count - 1))
{
curr_row = rows;
curr_col = cols;
}
}
}
}
void knight::print()
{
for (int row = 0; row < board_size; row++)
{
for (int col = 0; col < board_size; col++)
{
cout << knight_square[row][col] << " ";
}
cout << endl;
}
}
//Checks if board is solved
bool knight::is_solved()
{
for (int row = 0; row < board_size; row++)
{
for (int col = 0; col < board_size; col++)
{
if (knight_square[row][col] <= 0)
return false;
}
}
return true;
}Here is the main.
#include <iostream>
#include "knight.h"
using namespace std;
int main()
{
int size;
int start_row, start_col;
cout << "Enter the size of the board: " << endl;
cin >> size;
cout << "Enter the start position for the row: " << endl;
cin >> start_row;
cout << "Enter the start position for the column: " << endl;
cin >> start_col;
knight tour(size, start_row, start_col);
tour.solve_from(tour);
tour.print();
return 0;
}Here is the header file.
const int max_board = 6;
class knight {
public:
knight(int size, int start_row, int start_col);
void solve_from(knight &tour);
bool is_solved();
bool move(int row, int col);
void print();
void insert(int row, int col);
void remove(int row, int col);
int board_size;
private:
int count;
int curr_row, curr_col;
int knight_square[max_board][max_board];
};