I have a programming assignment to write the Knight's Tour. I have completed the code using simple recursive calls, my problem seems to be if the user enters any starting location the program takes longer then 45 minutes to complete and I am not sure if it even completes because after 45 minutes of having the program think I had to leave the lab and go to class. If anyone has any suggestions that can make it compute faster they will be greatly appreciated. I have attached the following code below. In case that attachments do not work I have also posted my code below:
BOARD.H
#ifndef BOARD_H // if the header file board.h is not defined
#define BOARD_H // then start defining board.h with the below code
#include <iostream> // allows the use of input and outputs in the program
using std::cout; // allows the use of cout from the standard library without having to put std:: each time
using std::cin; // allows the use of cin from the standard library without having to put std:: each time
using std::endl; // allows the use of endl from the standard library without having to put std:: each time
#include <iomanip> // allows the use of display manipulators in the program
using std::setw; // allows the use of setw from the standard library without having to put std:: each time
const int SUCCESS = 0; // indicates that the program has completed successfully
class Board{ // creates a class called Board
public: // everything below here the user has access to and can change
// Constructors/De-constructors
Board(); // default constructor
~Board(); // de-constructor
// Member Functions
void printBoard(); // function that prints out the 2D chess board
bool knightTour(int, int, int); // function that takes to integers and moves does the knight tour
private: // enverything below here the user does not have direct access to
int row;
int col;
int count; // creates and sets the variable count to 1; this will be the move number of the knight's tour
int board[8][8];
}; // end of class Board
#endif // stops defining board.h
**********************************
MAIN.CPP
// PRINTS OUT CORNERS FAST
#include "board.h" // allows the use of everything inside the header file
int main(){ // start of executable program
int row; // creates a variable row to hold a user input
int col; // creates a variable col to hold user input
int count = 1; // creates and sets the variable count to 1; this will be the move number of the knight's tour
Board p; // creates an object of class Board called p for its use to call the printBoard function
Board k; // creates an object of class Board called k; k will be used to call the knightTour function
cout << "Welcome to our Knight's Tour Program" << endl << endl; // display message shown to the user to let them know what the program is
p.printBoard(); // using the created class object p to call the printBoard function
cout << "The first number you enter will be the row the second number will be column" << endl;
cout << "Enter the starting location of the knight [from (0,0) to (7,7)]: "; // display message to user asking for input
cin >> row >> col; // reads the user input into the created variable slots
cout << "\nTest Echo Input\n" << "row: " << row << " " << "col: " << col << endl << endl; // test to make sur ethe user inputs are actually read into the program
/*if( k.knightTour(row,col,count) ){
p.printBoard();
} // end of if*/
if( k.knightTour(row,col,count) ){
k.printBoard();
} // end of if
else{
cout << "No path was found" << endl << endl;
} // end of else
return SUCCESS;
} // end of main
***************************
BOARD.CPP
#include "board.h" // allows the use of everything inside the header file
//==================
// OUTPUT(s): None
//
// INPUT(s): None
//
//==================
Board::Board(){ // this is the default constructor for the class Board
for( row = 0; row <= 7; row++ ){
for( col = 0; col <= 7; col++ ){
board[row][col] = 0;
} // end of inner for
} // end of outer for
} // end of constructor
//==================
// OUTPUT(s): None
//
// INPUT(s): None
//
//===================
Board::~Board(){ // this is the de-constructor for the class Board
} // end of de-constructor
//============================================
// OUTPUT(s): Prints out the 2D chess board
//
// INPUT(s): None
//
//============================================
void Board::printBoard(){ // function header for the function printBoard of class Board; taking no arguments
for( int i = 0; i <= 7; i++ ){ // sets an integer i to 0 and as long as i is less than or equal to 7 below is run, after below finished i is increased by 1
for( int j = 0; j <= 7; j++ ){ // sets an integer j to 0 and as long as j is less than or equal to 7 below is run; after below is finished running j is increased by 1
cout << setw(3) << board[i][j]; // takes the current location in the 2D array board and prints it to the screen; should print out a 8 by 8 board of 0's
} // end of inner for
cout << "\n\n"; // prints out blank lines for spacing
} // end of outer for
} // end of member function printBoard for class Board
//====================
// OUTPUT(s): ?
//
// INPUT(s): User inputs for the starting location of the knight
//
//====================
bool Board::knightTour(int row, int col, int count){ // function header for the function knightTour; taking the integer arguments of row and col that the user has entered
bool pathFound = false;
if( (row >= 0 && row <= 7) && (col >= 0 && col <= 7) ){ // if 1
if( board[row][col] == 0 ){ // if 2
board[row][col] = count;
if( count == 64 ){
pathFound = true;
} // end of if
if(!pathFound){ // if 3
pathFound = knightTour( row - 2, col + 1, count + 1 );
if( !pathFound ){
pathFound = knightTour( row - 1, col + 2, count + 1 );
} // end of if
if( !pathFound ){
pathFound = knightTour( row + 1, col + 2, count + 1 );
} // end of if
if( !pathFound ){
pathFound = knightTour( row + 2, col + 1, count + 1 );
} // end of if
if( !pathFound ){
pathFound = knightTour( row + 2, col - 1, count + 1 );
} // end of if
if( !pathFound ){
pathFound = knightTour( row + 1, col - 2, count + 1 );
} // end of if
if( !pathFound ){
pathFound = knightTour( row - 1, col - 2, count + 1 );
} // end of if
if( !pathFound ){
pathFound = knightTour( row - 2, col - 1, count + 1 );
} // end of if
if( !pathFound ){
board[row][col] = 0;
} // end of if
} // end of if 3
} // end of inner if 2
} // end of outer if 1
return (pathFound);
}; // end of member function knightTour for class Board
