Knight's tour using recursion and backtracking

[geeloso]

Hey guys!
I am writing a program to trace a knight's tour on a chess board using recursion and backtracking. The task is to make the knight travel through all the cells of the chess board, with each cell visited at most once. I have written pretty much all of the code for the program and have tested it. The results are encouraging but I am having a few problems. Shown below is the class definition and the definition of the recursive function.

Here are my questions, they mostly address what happens after backtracking:

Qn 1. Why are the contents of the queue in lines 36 and 45 different? In other words, why are the contents of the queue in line 45, when control is returning from a recursive call, different from those in line 36, even though both queues occur within the same recursive call? (no data was popped from the queue between the instances of the two statements!!)

Qn 2. Similarly, why is it that the value of noOfCellsFilled in line 38 not the same as that on line 52, after the recursive call?

class knightTour
{
public:
    knightTour(int = 0);
    bool canPlaceKnight(int&, int&, int);     //function to determine if knight can be placed in a particular cell on chess board 
    bool moveWithinBounds(int, int, int);     //function to determine if knight move is within the bounds of the chess board
    bool traceKnightTour(int, int);           //function to trace the path of the knight; all cells must be visited, each at most once
    void printKnightTour();
    pair <int, int> indexToKnightMoveConverter(int);
 
private:
    int noOfCellsFilled;
    int boardSize;
    int** chessBoard;
};



bool knightTour::traceKnightTour(int row, int col)
{ 
    if (noOfCellsFilled < boardSize*boardSize)       
    {
        if (noOfCellsFilled == 0)
	{
	    chessBoard[row][col] = 1;
	    ++noOfCellsFilled;
	}
	for (int i = 0; i < 8; i++)
	{    
	    if (canPlaceKnight(row, col, i))       //determines the row-column coordinates of knight's cell    
	    {  
	        static queue<pair<int,int> > q;    //queue to hold row-column coordinates of the current and last cell entries      
		q.push(make_pair(row, col));        
		if (q.size() > 2)		//ensuring the queue size is 2
	            q.pop();			
                showQueueContents(q);      //function to display the contents of the queue 
                
                chessBoard[row][col] = ++noOfCellsFilled;    //fill cell with corresponding number

                if (traceKnightTour(row, col))      //recursive call
	            return true;
                
	        chessBoard[row][col] = 0;     //backtracking
	            
                showQueueContents(q);      //displaying queue contents after recursive call     
	            pair<int, int> temp;         
                if (!q.empty())     
	            temp = q.front();      //since we are backtracking, retrieve row-column pair of last cell filled from the queue
                
                row = temp.first;         //grab the row-column coordinates of the last cell filled
                col = temp.second;	
                cout<<"noOfCellsFilled = "<<noOfCellsFilled<<endl;    
                --noOfCellsFilled;
	    }	         
	}
	return false;	    
    }
    else     //all the cells of the chess board are filled
        return true;   
}

[geeloso]

Does anyone have any insight into the questions I raised?

[BlackSheep]

You made q static. It gets initialized once, when traceKnightTour is called for the first time, and each subsequent call to traceKnightTour modifies the original copy. Its kind of like a global variable internal to the function.

So since you call traceKnightTour between 36 and 45, as well as between 38 and 52, you end up modifying the single queue<pair<int,int> > that gets shared between all calls to the funtion.

[geeloso]

Thanks for your response.
You wrote:

So since you call traceKnightTour between 36 and 45, as well as between 38 and 52, you end up modifying the single queue<pair<int,int> > that gets shared between all calls to the funtion.

I see what you are saying but my reasoning is this:

Function traceKnightTour(int,int) spans lines 19 to 60; at line 40, when the recursive call is encountered, a fresh function is invoked and a new set of local variables is created. The scope and duration of these variables are somewhere between lines 19 to 60, should the next recursive call return false. In order words, the unfinished execution of the statements following the IF block(recursive call) of line 40 just resumes. That is why I expected lines 45 and 52 to retain respectively what lines 36 and 38 had when line 40 returns false.

I only made q static in order to be able to access the row-col pair of the current recursive call during the next recursive call: the new position of the knight depends on its current position. Observe that the queue is constrained to size 2. The alternative would have been to pass the pair as a parameter to the function; but I am restricted from doing that!

Do you see my argument?

[mbozzi]

The scope and duration of these variables are somewhere between lines 19 to 60, should the next recursive call return false.

By default, the storage duration of a local variable is automatic, and the scope of the associated name is exactly from the point of declaration to the end of the lexically innermost block containing that declaration.

Your queue has static storage duration - it is persistent global state, with block scope; the same variable is shared between every call to that function. In C++, neither scope nor storage duration (not to be confused with lifetime) can depend on the state of the program. The behavior you're describing might appear in certain dynamic languages -- Common Lisp or Perl, for example -- but not C++.

A common pattern for solving this problem is to add a private steady-state recursive function with all the parameters you need, using the publicly visible function as a thunk:

public:
  bool traceKnightTour(int row, int col) 
  { traceKnightTour(row, col, std::queue<std::pair<int, int>>{}); }
private: 
  bool traceKnightTour(int, int, std::queue<std::pair<int, int>>) { ... }