Thread: Knight's Tour Recursion Problem

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    4

    Knight's Tour Recursion Problem

    Dear members,

    I'm having a problem with my recusrsion function in my Knight's Tour problem and I 've spent hours trying to figure out the solution yet to no avail.

    My problem is that when I simply have to step back and take another direction, It will run fine, but when I take one step back and have to take another then it just stops.

    Any help would be greatly appreciated, Thanks in advance.

    p.s.for example, use beginning postion row 8 column 8. See what happens when you reach move 53 (movecount = 52)
    Code:
    #include <iostream>
    #include <iomanip>
    #include <time.h>
    
    using std::cout;
    using std::cin;
    using std::endl;
    using std::setw;
    
    const long MaxRows = 8;
    const long MaxColumns = 8;
    
    const long HorizontalMoves[] = { 2, 1,-1,-2,-2,-1, 1, 2};
    const long VerticalMoves[] =   {-1,-2,-2,-1, 1, 2, 2, 1};
    
    void GetFirstPosition(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[]);
    void InitializeBoard(long Board[][MaxColumns]);
    void PrintBoard(long Board[][MaxColumns]);
    void FindNextMove(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long MoveIndex);
    void BackTrack(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long& MoveIndex);
    bool OnBoard(long Row, long Column);
    
    int main(void)
    {
    	long CurrentRow = 0;
    	long CurrentColumn = 0;
    	long MoveCount = 0;
    	long Board[MaxRows][MaxColumns] = {0};
    	long RowMoveHistory[64];
    	long ColumnMoveHistory[64];
    	long DirectionHistory[64];
    	long MoveIndex = 0;
    
    	InitializeBoard(Board);
    	PrintBoard(Board);
    	GetFirstPosition(Board, CurrentRow, CurrentColumn, MoveCount, RowMoveHistory, ColumnMoveHistory, DirectionHistory);	
    	PrintBoard(Board);
    
    	do
    	{
    		FindNextMove(Board, CurrentRow, CurrentColumn, MoveCount, RowMoveHistory, ColumnMoveHistory, DirectionHistory, MoveIndex);
    		
    
    	}
    	while(MoveCount < 65);
    
    	cout << "Your knight made it to all 64 squares!" << endl;
    
    
    	return 0;
    }
    
    void FindNextMove(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long MoveIndex)
    {
    
    	bool MoveFound = 0;
        while(MoveFound == 0)
    	{	
    
    		if(OnBoard((CurrentRow + VerticalMoves[MoveIndex]), (CurrentColumn + HorizontalMoves[MoveIndex])) == 1 && Board[CurrentRow + VerticalMoves[MoveIndex]][CurrentColumn + HorizontalMoves[MoveIndex]] == 0)
    	{
    					
    		CurrentRow += VerticalMoves[MoveIndex];
    		CurrentColumn += HorizontalMoves[MoveIndex];
    		Board[CurrentRow][CurrentColumn] = MoveCount + 1;
    		
    		MoveFound = true;
    
    		DirectionHistory[MoveCount] = MoveIndex;
    		RowMoveHistory[MoveCount] = CurrentRow;
    		ColumnMoveHistory[MoveCount] = CurrentColumn;
    		MoveCount++;
    		MoveIndex = 0;		
    
    	}
    	else
    	{
    		MoveIndex++;
    
    		if(MoveIndex == 8)
    		{
    		
    PrintBoard(Board);
    system("pause");		
    		BackTrack(Board, CurrentRow, CurrentColumn, MoveCount, RowMoveHistory, ColumnMoveHistory, DirectionHistory, MoveIndex);
    		
    		
    		}
    		
    	}
    	
    
    	
    	}
    
    
    	}
    		
    		
    
    
    void BackTrack(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[], long& MoveIndex)
    {
    	
    	
    MoveCount--;
    		PrintBoard(Board);
    		CurrentRow -= VerticalMoves[DirectionHistory[MoveCount]];
    		CurrentColumn -= HorizontalMoves[DirectionHistory[MoveCount]];
    		Board[RowMoveHistory[MoveCount]][ColumnMoveHistory[MoveCount]] = 0;
    
    		Board[CurrentRow][CurrentColumn] = MoveCount;
    
    		MoveIndex = DirectionHistory[MoveCount - 1] + 1;
    		RowMoveHistory[MoveCount] = 0;
    		ColumnMoveHistory[MoveCount] = 0;
    		DirectionHistory[MoveCount - 2] = 0;
    
    if(MoveIndex == 8)
    MoveIndex = 0;
    		
    	
    		
    		
    
    	
    
    	system("pause");	
    
    	
    }
    
    void InitializeBoard(long Board[][MaxColumns])
    {
    	for (long Row = 0; Row < MaxRows; Row++)
    	{
    		for (long Column = 0; Column < MaxColumns; Column++)
    		{
    			Board[Row][Column] = 0;
    		}
    	}
    }
    
    void PrintBoard(long Board[][MaxColumns])
    {
    	system("cls");
    
    	cout << "     1  2  3  4  5  6  7  8" << endl;
    	cout << "   ------------------------" << endl;
    	
    	for (long Row = 0; Row < MaxRows; Row++)
    	{
    		cout << Row + 1 << "| ";
    
    		for (long Column = 0; Column < MaxRows; Column++)
    		{
    			cout << setw(3) << Board[Row][Column];
    		}
    
    		cout << endl;
    	}
    }
    
    void GetFirstPosition(long Board[][MaxColumns], long& CurrentRow, long& CurrentColumn, long& MoveCount, long RowMoveHistory[], long ColumnMoveHistory[], long DirectionHistory[])
    {
    	bool MoveFound = false;
    	int MoveIndex = 0;
    	do
    	{
        cout << endl << "Where do you wish to begin?" << endl;
    	cout << "Row: ";
    	cin >> CurrentRow;
    	cout << "Column: ";
    	cin >> CurrentColumn;
    	}
    	while(CurrentRow == 0 || CurrentRow == 0 || CurrentRow > 8 || CurrentColumn > 8);
    
    	CurrentRow -= 1;
    	CurrentColumn -=1;
    
    		while(MoveFound == false)
    		{
    
    		if(OnBoard((CurrentRow + VerticalMoves[MoveIndex]), (CurrentColumn + HorizontalMoves[MoveIndex])) == 1 && Board[CurrentRow + VerticalMoves[MoveIndex]][CurrentColumn + HorizontalMoves[MoveIndex]] == 0)
    		{
    			Board[CurrentRow][CurrentColumn] = MoveCount + 1;
    			MoveFound = true;
    		}
    		else
    		{
    			MoveIndex++;
    		}
    	}
    
    		RowMoveHistory[MoveCount] = CurrentRow;
    		ColumnMoveHistory[MoveCount] = CurrentColumn;
    		DirectionHistory[MoveCount] = MoveIndex;
    
    	MoveCount++;	
    }
    
    bool OnBoard(long Row, long Column)
    {
    
    	bool Result = false;
    
    	if (Row >= 0 && Row < 8 && Column >= 0 && Column < 8)
    	{
    		Result = true;
    	}
    
    	
    	return Result;
    
    }

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I've only briefly looked at it so maybe somewhere you do take care of this and I missed it, but each square needs it's own move index. Otherwise when you backtrack that new square will use the moveindex of a different square meaning it is possible it won't check all of the possibilities or (and I think this is the error you are getting) it will check the same direction over and over again making it look like it is doing nothing.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion problem
    By trnd in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 03:06 PM
  3. simple Recursion problem
    By wOo[FIN.K.L] in forum C Programming
    Replies: 8
    Last Post: 06-12-2008, 05:58 AM
  4. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 03:52 PM
  5. recursion problem!!
    By newbie_grg in forum C++ Programming
    Replies: 5
    Last Post: 07-30-2002, 01:37 PM