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

I posted an Identical thread in c fourum & but mine was faster though. It takes a few minutes to find a combination. & then to improve the performance, I'll give the same link I recived Warnsdorff's Algorithm

Thank you I will check it out.

too bad most people on here don't have membership to ACM.

commented: gtfo troll +0

The first reply is actually a better page for this question, so I'll take that to mean you just like posting flamebait.

what, does everyone here have an ACM membership?

am i the only one who doesnt?

because i was interested in your links, so i went to check it out (the one about Hamilton Paths)

and well, guess what? I need to pay $99.00 in order to access your article.

so, instead of you getting all clenched up at the slightest bit of justified criticism, maybe you ought to consider your audience when you post links.

I mean, yeah, I could go and post all sorts of links to IEEE peer-reviewed journal articles... but i dont. ... for obvious reasons.

and by the way, great way to introduce yourself. welcome to the community.

.

[edit] this doesn't belong on this board :) [/edit]

[edit] this doesn't belong on this board :) [/edit]

and neither do those $99.00 links :)

.

Here you go:
<snipped link>

Those ACM links are probably pretty useless to the OP. Not unless he has a Masters or Ph.D. in computer science or something which I doubt.

{post delete button}

Hey Buddha.

here's an implementation of the Knight's Tour i wrote in C. the algorithm is a simple one (Warnsdorff). it's a couple hundred years old, so it's not plagiarism to use it, i dont think..

at any rate, it solves any position for "open" and "closed" solutions. not the best, but it will give you an answer in a second or two. i have additional delay incurred from repeatedly printing to console.

check it out and see how you might apply it to your own C++ problem.

and to the experts: maybe someone can tell me why this algorithm occasionally fails? i thought it was pretty bulletproof, but every now and then it will paint itself into a corner.

here's the program along with with a ZIP of the MSVC-compiled executable and C source

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum Direction {
    FwdRight,
    RightFwd,
    RightBack,
    BackRight,
    BackLeft,
    LeftBack,
    LeftFwd,
    FwdLeft
};

void printBoard(char * marks, int turn);
int initialize(char *board);
int convertIndexToRowCol(int index, int *row, int *col);
int convertRowColToIndex(int row, int col, int *index);
int convertNameToIndex(char *name, int *index);
char * convertIndexToName(int index);
int findAvailMoves(int position, char *board, int *moves);
int bestWarnsdorff(int position, char *board, int * movesAvail);
int promptAndReply(char * message, char * response, int responseLen);
void stringToUpper (char *buffer);
void getCommandLineArgs(int argc, char **argv);


int ARG_Debug = 0;  // if command line arg "ARG_Debug" is given, each step
                    // of the move selection process will be displayed

main(int argc, char **argv)
{
    char boardState[64], tmp[3];
    int movesAvail[8], turns, validMoves, curPos, newPos, trace=0;
    int a, openWin=0, closedWin=0, lost=0;

    srand ((unsigned)time(NULL));   // seed pseudo-random generator
    getCommandLineArgs(argc,argv);  // check command line

    do {

        // clear board position index, get initial (start) pos from user
        curPos = newPos = 0; turns = 1;
        memset(boardState, 0, 64);
        curPos = initialize(boardState);

        while (curPos != -1)  // continue unless error
        {
            // from current position, find number of valid moves available
            validMoves = findAvailMoves(curPos,boardState,movesAvail);

            if (validMoves == 0)  // tour is done, no moves available
                break;            // break from while() loop

            if (++turns > 64)     // can only occur on a "closed win"
                break;

            // of the valid moves available, find which is "best"
            newPos = bestWarnsdorff(curPos,boardState,movesAvail);

            boardState[newPos] = turns;    // move to that best position
            printBoard(boardState, turns); // redraw new board state
            curPos = newPos;               // new best postion -> current
            // if all squares have been toured, clear initial position
            // if it can be attacked, is "closed win", otherwise "open"
            if (turns==64)
                for (a=0; a<64; a++)
                    if (boardState[a]==1)  // found the initial position
                    {
                        boardState[a]=0;   // clear it
                        break;             // done here, break from FOR
                    }
        }
        printf("    Final Pos:  %s\n    Result   :  ",
                                            convertIndexToName(curPos));

        if (turns==65) // if inital pos a valid move after the 64th turn
        {
            printf("CLOSED WIN !!!\n");
            closedWin++;
        }
        else if (turns==64)
        {
            printf("Open Win\n");
            openWin++;
        }
        else if (curPos != -1)  // "quit to exit" is not a failure
        {
            printf("well, crap...\n");
            lost++;
        }
        else
            printf("User Quit\n");

        printf("    Totals   :  Closed %d, Open %d, Lost %d\n\n",
                                            closedWin, openWin, lost);
        promptAndReply("hit <enter> to continue ",tmp, sizeof(tmp));

    }
    while (curPos != -1);
    printf("Bye.\n");

}


int bestWarnsdorff(int position, char *board, int * movesAvail)
//  uses the Warnsdorff Algorithm to determine "best" of all available
//  moves with goal of completing the Knight's Tour.  If there two or
//  more equally "best" moves, one will be chosen randomly.  This 
//  allows "open solutions" to occur more often than "closed solutions"
//  Choosing among equally "best" moves to prefer a closed solution is
//  beyond scope of Warnsdorff's Algorithm
//
//  input:  position (1D index value) of the Knight's current location
//          board array indicating state of all spaces on board
//          movesAvail array showing which directions valid/available
//
//  return: 1D index value of the "best" board position for next move
{
    int newPos, bestMove, score, bestScore, numBest,
        direction, locations[8];
    double pct, rval;
    char tmp[3];

    bestScore = 9;   // start high possible, better scores will be lower
    numBest = 1;     // number of equally-lowest (best) scores found

    //check each of the 8 ordinal directions Knight is able to move
    for (direction=0; direction<8; direction++)
    {
        // if direction is valid/available, it will be the index number
        // of the position (0-63) of the resulting move
        newPos = movesAvail[direction];
        if (newPos >= 0)
        {
            // grade the new position to how many "entrances" it has
            score = findAvailMoves(newPos,board,locations);
            if (ARG_Debug)
                printf("move to %s score %d\n",
                                    convertIndexToName(newPos),score);
            if (score < bestScore)  // new position with lowest score
            {
                numBest=1;          // reset count of equally low scores
                bestScore = score;  // new score becomes the best score
                bestMove = newPos;  // new position becomes the new best
            }
            else if (score == bestScore)// if new best equals current
            {                           // choose between the two bests
                pct = 1.0/++numBest;    // based on number of ties
                rval = (double)rand() / (double)RAND_MAX;
                if (rval < pct)         // if random # is within % chance
                    bestMove = newPos;  // replace current best w/ new
            }
        }
    }
    if (ARG_Debug)
    {
        printf(" ... selected %s",convertIndexToName(bestMove));
        promptAndReply("",tmp, sizeof(tmp));
    }

    return bestMove;
}


int findAvailMoves(int position, char *board, int *moves)
//  using current position, check each of the 8 ordinal directions that a
//  knight can move, whether the direction lands on a valid and available
//  space.  invalid moves land off board.  unavailable moves land on
//  spaces that have already been "toured"
//
//  input:  "position" of knight described as 1D board array index (0-63)
//          "board" array describing current state of all board positions
//
//  output: "moves" array describing each of 8 ordinal directions the
//             knight could conceivably move.  if the move is invalid or
//             unavailable, the element is flagged -1 or -2
//             if the move is valid and available element written with 1D
//             board array index value (0-63) of resulting space
//
//  return: numeric value between 0 and 8 of the total number of valid and
//             available moves from the current position.
//          if an error occurs, the return value will be 0.
{
    enum Direction direction;
    int row,col,index, numAvailable;

    numAvailable=0;  // count of valid and available moves

    for (direction=0; direction<8; direction++)
    {   // convert 1D index to 2D row and column values
        convertIndexToRowCol(position, &row,&col);
        switch (direction)  // based on each direction, calculate where
        {                   // each move would land
            case (FwdRight):
                row+=2; col++;
                break;

            case (RightFwd):
                row++; col+=2;
                break;

            case (RightBack):
                row--; col+=2;
                break;

            case (BackRight):
                row-=2; col++;
                break;

            case (BackLeft):
                row-=2; col--;
                break;

            case (LeftBack):
                row--; col-=2;
                break;

            case (LeftFwd):
                row++; col-=2;
                break;

            case (FwdLeft):
                row+=2; col--;
                break;

            default :   // invalid input returns zero, ending program
                printf("  ***  FindAvailMove: switch statement Error!\n");
                return 0;
        }
        // check if the new row and/or column are out of bounds
        if (convertRowColToIndex(row, col, &index) == -1)
            moves[direction]=-1;    // flag direction as invalid

        // check if position was marked as "toured" from a previous turn
        else if (board[index]>0)
            moves[direction]=-2;    // flag direction as unavailable

        else  // move is valid and available
        {
            moves[direction]=index;
            numAvailable++;
        }
    }
    return numAvailable;
}


int convertIndexToRowCol(int index, int *row, int *col)
// convert the 1D board array index to corresponding row and column values
//
// input:  index for board array is a value from 0-63
//
// output: row is value from 0-7
//         col is value from 0-7
//
// return  0 if success, -1 if invalid input
{
    if (index < 0 || index > 63)
        return -1;

    *row = index / 8;
    *col = index % 8;

    return 0;
}


int convertRowColToIndex(int row, int col, int *index)
// convert row and column values to corresponding 1D board array index
//
// input : row is value from 0-7
//         col is value from 0-7
//
// output: index for board array is a value from 0-63
//
// return: 0 if success, -1 if invalid input
{
    if (row<0 || col<0 || row>7 || col>7)
        return -1;

    *index = row*8 + col;

    return 0;
}


int convertNameToIndex(char *name, int *index)
//  take the standard (algebraic) space name ("A2", "D4", etc)
//  convert to the 1D board array index number
//
//  input:  pointer to NAME as ascii string, "A2", "D4", etc.
//
//  output: 1D board array index value (0-63) or the flag value 999
//             to indicate the user "quit" command was given
//
//  return: 0 if success (including "quit"), -1 if invalid input
{
    char spaceName[3];

    //copy only the first two characters, ensure first is capitalized
    strncpy(spaceName,name,2);
    spaceName[3]=0;
    spaceName[0]=toupper(spaceName[0]);

    //only columns A-H & rows 1-8 (algebraic chess notation) are valid
    if (spaceName[0] >= 'A' &&
        spaceName[0] <= 'H' &&
        spaceName[1] >  '0' &&
        spaceName[1] <  '9'
       )
        *index = (spaceName[1]-0x31) * 8 + spaceName[0]-0x41;   // 0-63

    // exception for the first letter "Q" of user "quit" command
    else if (spaceName[0] == 'Q')
        *index = 999;

    else
    {
        printf("  ***  Error: \'%s\' is invalid\n",spaceName);
        *index = -1;
    }

    return (*index >= 0) ? 0 : -1;  // 0 if success, -1 fail
}


char * convertIndexToName(int index)
//  take the 1D array index number, convert it to the
//  standard (algebraic) space name ("A2", "D4", etc)
//
//  input:  1D board array index value (0-63)
//
//  return: pointer to NAME as ascii string, "A2", "D4", etc.
//          or NULL if invalid input

{
    static char name[3];

    if (index<0 || index > 63)
        return NULL;  // invalid index value
    name[0] = (index % 8) + 0x41;
    name[1] = (index / 8) + 0x31;
    name[2] = 0;

    return name;
}


void printBoard(char * marks, int turn)
//  prints the entire board and marks all postions visited
//  use unique marks for the current Knight position.
//
//  input: requires board array (marks)
//         current turn number
//
//  outputs and returns nothing
//
{
    int row, col, index;

    system("cls");
    printf("   Knight's Tour     Turn %d\n",turn);
    printf("    -----------------------\n");

    for (row=7; row>=0; row--)
    {
        printf(" %d |",row+1);
        for (col=0; col<8; col++)
        {
            convertRowColToIndex(row, col, &index);

            if (marks[index] == turn)   // mark the knight's current space
                printf("><");

            else if (marks[index]) // mark the turn space was visited
                printf("%2d",marks[index]);

            else                   // leave blank, if not
                printf("  ");

            if (col==7)
                printf("|\n");
            else
                printf(" ");
        }
        if (row)
            printf("   |  +  +  +  +  +  +  +  |\n");
    }
    printf("    -----------------------\n");
    printf("    A  B  C  D  E  F  G  H\n\n");

}


int initialize(char *board)
//  starts the clean board and prompts user to choose start position
//
//  output: updates array of board data via pointer
//
//  return  the 0-63 index value of the chosen start position if success
//           -1 if function failed
{
    char startPos[32];
    int startIndex=-1;

    do
    {
        printBoard(board,1);
        promptAndReply("\n\nChoose starting position or \"q\" to quit : ",
                                            startPos, sizeof(startPos));
    }
    while(convertNameToIndex(startPos,&startIndex));  // return 0 success


    if ( startIndex >= 0 && startIndex < 64)
    {
        board[startIndex] = 1;  // "turn" number 1 is starting position
        printBoard(board,1);    // prints entire board, turn number = 1
        return startIndex;
    }
    else
        return -1;

}


int promptAndReply(char * message, char * response, int responseLen)
// prints prompt message to terminal, waits for input from user
//
// inputs:  pointer to message string that prompts the user response
//          maximum response string length (sizeof)
//
// outputs: pointer to null-terminated response string
//             NOTE: any newline characters will be stripped
//
// returns: 0 if full user response was successfully read and stored
//          1 if any bytes still remain after input was processed.
//          -1 if failure caused any other error
//
// notes:   if a positive value is returned, the user input more
//          characters than the calling routine anticipated.
//          the caller is responsible for performing additional
//          input processing on any remaining characters
{
    char *buffer, *buff_ptr;
    int remain=1;

    buffer = (char*) malloc (responseLen);
    buff_ptr = buffer;

    printf("%s",message);
    fgets(buffer,responseLen-1,stdin);

    //newline read from stdin indicates end of user data
    //delete the newline character(s).
    //return flag indicates no data remains
    while(*buff_ptr)
    {
        if (*buff_ptr == 0x0D || *buff_ptr == 0x0A)
        {
            remain = 0;
            *buff_ptr = 0;
        }
        buff_ptr++;
    }

    strcpy(response,buffer);
    free(buffer);

    return remain;
}

void stringToUpper (char *buffer)
// converts any lowercase characters in a string to uppercase
// leaves non-lowercase and non-alpha character as they were
//
//

{
    char * buffer_ptr = buffer;
    size_t buffer_len = strlen(buffer);

    while(buffer_len--)
        *buffer_ptr=toupper(*buffer_ptr++);
}

void getCommandLineArgs(int argc, char **argv)
// parse all command line arguments each in turn
// matching against expected values and setting
// global variables accordingly.
//
// inputs:  argc and argv from main()
//
// notes:  currently only "ARG_Debug" is being checked.
//         more argumetns can be added as desired
//         arguments have a maximum length of 15 chars
//         arguments are case insensitive
{
    int a, argLen;
    char argStr[16];

    if (argc>1)   // parse command line arguments
    {
        printf("\nparsing command line args:\n\n");
        for (a=1; a<argc; a++)
        {
            argLen = (strlen(argv[a])>15)?15:strlen(argv[a]);
            strncpy(argStr,argv[a],argLen);
            argStr[argLen]=0;
            stringToUpper(argStr);

            if (strncmp(argStr,"ARG_Debug",5)==0)
                ARG_Debug=1;
            //add additional arguments as needed

            printf("    arg[%d] = %s\n",a,argStr);

        }
        promptAndReply("\nhit <enter> to continue ...",argStr,3);
    }
}

.

Thank you very much jephthah, this looks like it will help me think about how to fix my own program to be a bit faster.

focus on "findAvailMoves" and "bestWarnsdorff" subroutines.

that's where the action is.

whoops. line 515 is wrong. it should be:

515. if (strncmp(argStr,"DEBUG",5)==0) .

Thanks jephthah your code was very helpful in making my output faster I just handed in my program so hopefully its acceptable enough for my professor.

ah cool. so did you get improvement in speed?

i see that your assignment was really more focused on the recursion... my code didnt even address that at all.

anyway, i just thought id post it, maybe it'll be of use somewhere. i got kind of obsessed about completing it :P

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.